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