It is a beautiful Sunday morning in Minneapolis, MN part of a long Labor Day weekend. Spent some time in the past couple days working on solving a HackerRank problem named QHEAP1. I want to discuss my approach and the reason I solved the problem twice. No, it was not get double points solving the same problem. I do not believe you can do that. Once a problem is solved it is flagged.

I always tend to refresh my knowledge (in this case) or learn about a new topic in order to better understand it before attempting to design a solution. You would be surprised how many people just looks for a solution on-line and never understand what they did or the ramifications if it is not just a standalone problem (i.e., HackerRank) but it is part of an application or system.

I did some poking around on-line using Google Chrome. I then turned into “Introduction to Algorithms” by Thomas Cormet et al and to “The Art of Computing Programming” by Donald Knuth. A binary heap is a **complete binary tree** which **satisfies the heap ordering property**. The ordering can be one of two types:

Property |
Description |

min-heap | The value of each node is greater than or equal to the value of its parent, with the minimum-value element at the root. |

max-heap | The value of each node is less than or equal to the value of its parent, with the maximum-value element at the root. |

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

The problem is described as follows: A set of Q queries is given to the performed against a heap. The queries are defined as follows:

Query |
Description |

1 v | Add the specified element (v) to the heap. |

2 v | Delete the specified (v) element from the heap. |

3 | Print the value of minimum element in the heap. |

If you wish to read more about the problems please take a look at: **https://www.hackerrank.com/challenges/qheap1**

In most languages Priority Queues are implemented using a heap. Most (if not all) languages encapsulate the operation of a class. By using the PriorityQueue one could easily and quickly solve the problem without having the foggiest idea of what a heap is and how to implement one.

If you are a software developer and have to get a job done as soon as possible and keep management happy you could go the PriorityQueue class route. As a matter of fact, most organizations seem to lean for such an approach. The task is done and seems to work so move on to the next one.

On the other hand, spending some time understanding how something works is quite beneficial for the individual’s knowledge and for the quality of the resulting software. Of course, do not take a few days when something could be done in no more than a few hours. Software development is always a struggle for balance between time and cost against the goal of producing quality software.

Given that I am using HackerRank as a learning tool, I decided to solve the problem twice. I was first inclined to use the PriorityQueue class, but then changed my mind and went for the solution using an array. My code follows:

**import** java.util.Scanner;

**class** Heap {

**int** length = 0;

**int** heapSize = 0;

**int**[] arr = **null**;

**public** Heap() {

**this**.length = 100000;

**this**.heapSize = 0;

arr = **new** **int**[length];

**for** (**int** i = 0; i < arr.length; i++) {

arr[i] = Integer.** MAX_VALUE**;

}

}

}

**public** **class** Solution {

// **** methods ****

**static** **int** left(**int** i) {

**return** 2 * i;

}

**static** **int** right(**int** i) {

**return** (2 * i) + 1;

}

**static** **void** exchange(Heap heap, **int** i, **int** j) {

**int** temp = heap.arr[i];

heap.arr[i] = heap.arr[j];

heap.arr[j] = temp;

}

**static** **void** heapify(Heap heap, **int** i) {

**int** smallest = 0;

**int** l = *left*(i);

**int** r = *right*(i);

// **** determine if smallest is on left … ****

**if** ((l <= heap.heapSize) && (heap.arr[l] < heap.arr[i])) {

smallest = l;

} **else** {

smallest = i;

}

// **** … or smallest is on right ****

**if** ((r <= heap.heapSize) && (heap.arr[r] < heap.arr[smallest])) {

smallest = r;

}

// **** exchange if needed ****

**if** (smallest != i) {

*exchange*(heap, i, smallest);

*heapify*(heap, smallest);

}

}

**static** **int** search(Heap heap, **int** v) {

**for** (**int** i = 1; i <= heap.heapSize; i++) {

**if** (heap.arr[i] == v) {

**return** i;

}

}

System.** out**.println(“<<< v: ” + v + ” NOT found !!!”);

**return** -1;

}

**static** **void** minHeap(Heap heap) {

**for** (**int** pos = (heap.heapSize / 2); pos >= 1; pos–) {

*heapify*(heap, pos);

}

}

**static** **void** add(Heap heap, **int** v) {

heap.heapSize += 1;

heap.arr[heap.heapSize] = v;

*minHeap*(heap);

}

**static** **void** delete(Heap heap, **int** v) {

**int** i = *search*(heap, v);

**if** (i <= 0) {

System.** out**.println(“<<< UNEXPECTED i: ” + i + ” v: ” + v);

**return**;

}

heap.arr[i] = Integer.** MAX_VALUE**;

*exchange*(heap, i, heap.heapSize);

heap.heapSize–;

*minHeap*(heap);

}

**static** **void** print(Heap heap) {

System.** out**.println(heap.arr[1]);

}

**static** **void** dump(Heap heap) {

System.** out**.print(“<<< “);

**for** (**int** i = 1; i <= heap.heapSize; i++) {

System.** out**.print(heap.arr[i] + ” “);

}

System.** out**.println();

}

**public** **static** **void** main(String[] args) {

**int** v = -1;

**int** query = -1;

Heap heap = **new** Heap();

Scanner sc = **new** Scanner(System.** in**);

**int** Q = sc.nextInt();

// **** loop once per query ****

**for** (**int** q = 0; q < Q; q++) {

query = sc.nextInt();

**if** (query <= 2) {

v = sc.nextInt();

}

**switch** (query) {

**case** 1:

*add*(heap, v);

**break**;

**case** 2:

*delete*(heap, v);

**break**;

**case** 3:

*print*(heap);

**break**;

}

}

// **** ****

sc.close();

}

}

After verifying the solution, I went back and implemented it using a Java PriorityQueue. My solution follows:

**import** java.util.Iterator;

**import** java.util.PriorityQueue;

**import** java.util.Scanner;

**public** **class** Solution {

**public** **static** **void** main(String[] args) {

PriorityQueue<Integer> heap = **new** PriorityQueue<Integer>();

Scanner sc = **new** Scanner(System.** in**);

**int** Q = sc.nextInt();

**int** v = -1;

**for** (**int** q = 0; q < Q; q++) {

**int** query = sc.nextInt();

**switch** (query) {

**case** 1:

v = sc.nextInt();

heap.add(v);

**break**;

**case** 2:

v = sc.nextInt();

Iterator<Integer> it = heap.iterator();

**while** (it.hasNext()) {

**int** x = it.next().intValue();

**if** (v == x) {

heap.remove(x);

**break**;

}

}

**break**;

**case** 3:

System.** out**.println(heap.peek());

**break**;

}

}

sc.close();

}

}

I have to agree that from a maintenance point of view, small code tends to be easy to understand and maintain. The second approach is about an order of magnitude shorter. I did not spend the time to run performance tests. If you find the time to experiment with these solutions please let me know your results.

**At the end of the day, I am glad I spent time experimenting with heaps and priority queues.**

John

john.canessa@gmail.com