12 Heap Interview Questions (SOLVED) For Your Next Coding Interview

A Heap is a special Tree-based data structure which is an almost complete tree that satisfies the heap property:

• in a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C.
• In a min heap, the key of P is less than or equal to the key of C. The node at the "top" of the heap (with no parents) is called the root node.

A common implementation of a heap is the binary heap, in which the tree is a binary tree.

A priority queue is a data structure that stores priorities (comparable values) and perhaps associated information. A priority queue is different from a "normal" queue, because instead of being a "first-in-first-out" data structure, values come out in order by priority. Think of a priority queue as a kind of bag that holds priorities. You can put one in, and you can take out the current highest priority.

A binary heaps are commonly implemented with an array. Any binary tree can be stored in an array, but because a binary heap is always a complete binary tree, it can be stored compactly. No space is required for pointers; instead, the parent and children of each node can be found by arithmetic on array indices:

• The root element is 0
• Left child : (2*i)+1
• Right child : (2*i)+2
• Parent child : (i-1)/2

A binary heap is defined as a binary tree with two additional constraints:

• Shape property: a binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
• Heap property: the key stored in each node is either greater than or equal to (≥) or less than or equal to (≤) the keys in the node's children, according to some total order.

We start adding child from the most left node and if the parent is lower than the newly added child than we replace them. And like so will go on until the child got the parent having value greater than it.

Your initial tree is:

     77
    /  \
   /    \
  50    60
 / \    / \
22 30  44 55

Now adding 55 according to the rule on most left side:

     77
    /  \
   /    \
  50    60
 / \    / \
22 30  44 55
/
55

But you see 22 is lower than 55 so replaced it:

       77
      /  \
     /    \
    50    60
   / \    / \
  55 30  44 55
 /
22 

Now 55 has become the child of 50 which is still lower than 55 so replace them too:

       77
      /  \
     /    \
    55    60
   / \    / \
  50 30  44 55
 /
22

Now it cant be sorted more because 77 is greater than 55.

A Binary Heap is a Binary Tree with following properties:

• It’s a complete tree (all levels are completely filled except possibly the last level and the last level has all keys as left as possible). This property of Binary Heap makes them suitable to be stored in an array.
• A Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at root must be minimum among all keys present in Binary Heap. The same property must be recursively true for all nodes in Binary Tree. Max Binary Heap is similar to MinHeap.

            10                      10
         /      \               /       \  
       20        100          15         30  
      /                      /  \        /  \
    30                     40    50    100   40

Heap is generally preferred for priority queue implementation because heaps provide better performance compared arrays or linked lists:

• In Array:
• insert() operation can be implemented by adding an item at end of array in O(1) time.
• getMax() operation can be implemented by linearly searching the highest priority item in array. This operation takes O(n) time.
• deleteMax() operation can be implemented by first linearly searching an item, then removing the item by moving all subsequent items one position back.

• In a Binary Heap:
• getMax() can be implemented in O(1) time,
• insert() can be implemented in O(log n) time and
• deleteMax() can also be implemented in O(log n) time.

Heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum.

A heap is a complete binary tree (every level filled as much as possible beginning at the left side of the tree) that follows this condition: the value of a parent element is always greater than the values of its left and right child elements. So, by taking advantage of this property, we can pop off the max of the heap repeatedly and establish a sorted array.

In an array representation of a heap binary tree, this essentially means that for a parent element with an index of i, its value must be greater than its left child [2i+1] and right child [2i+2] (if it has one).

The HeapSort steps are:

• Create a max heap from the unsorted list
• Swap the max element, located at the root, with the last element
• Re-heapify or rebalance the array again to establish the max heap order. The new root is likely not in its correct place.
• Repeat Steps 2–3 until complete (when the list size is 1)

Visualisation:

Complexity:

Priority Queue abstract data type (ADT) can be implemented using other data structures (including Heaps) like:

• Unordered Array
• Unordered List
• Ordered Array
• Ordered List
• Binary Search Tree (BST)
• Balanced Binary Search Tree (AVL-tree)
• Binary heap

Compare the time efficiency of heap implementation for main operations in Priority Queue ADT with other possible implementations:

----------------------------------------------------------------------------
| Implementation | Insertion   | Deletion(DeleteMax/DeleteMin)|Find Max/Min
----------------------------------------------------------------------------
| Unordered Array| 1           | n                            | n
----------------------------------------------------------------------------
| Unordered List | 1           | n                            | n
----------------------------------------------------------------------------
| Ordered Array  | n           | 1                            | 1
----------------------------------------------------------------------------
| Ordered List   | n           | 1                            | 1
----------------------------------------------------------------------------
| BST            | logn (avg.) | logn (avg.)                  | logn (avg.)
----------------------------------------------------------------------------
| Balanced BST   | log n       | log n                        | log n
----------------------------------------------------------------------------
| Binary Heaps   | log n       | log n                        | 1

find-min (resp. find-max), delete-min (resp. delete-max) and insert are the three most important operations of a min-heap (resp. max-heap), and they usually have complexity of O(1), O(log n) and O(log n) respectively if you implement a min/max-heap by a binary tree.

Now suppose instead you implement a min-heap by a sorted (non-decreasing) array (The case for max-heap is similar). find-min and delete-min are of O(1) complexity if insert is not required in your application, since you can maintain a pointer p that always points to the minimum element in your array. When the minimum element is removed, you just need to move p one step to the next element in the array.

Dealing with insertion in a sorted array is not trivial. Given a new element e, we can use binary search to locate its position in the array to insert it. But the point is that if you want to insert it there, you have to move a lot of old elements (can be O(n)) around to make a vacancy for the new element to reside. This is quite inefficient for most applications. You may also choose to re-sort the array after an element is inserted, this requires O(n log n) time however.

Where a heap absolutely, completely beats sorting arrays is a situation where small numbers of items are removed or added, and after each change you want to know again which is the smallest element.

The characteristic of a heap is that it is a structure that maintains data semiordered; thus, it is a good tradeoff between the cost of maintaining a complete order ant the cost of seaching through random chaos. That characteristic is used on many algorithms, such as selection, ordering, or classification.

Also consider:

• Use it whenever you need quick access to the largest (or smallest) item, because that item will always be the first element in the array or at the root of the tree
• Good for selection algorithms (finding the min or max). A heap allows access to the min or max element in constant time, and other selections (such as median or kth-element) can be done in sub-linear time on data that is in a heap
• Priority Queue. A priority queue is an abstract concept like "a list" or "a map"; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods.
• Anytime when you sort a temporary list, you should consider heaps. Heapsort is one of the best sorting methods being in-place and with no quadratic worst-case scenarios.
• A heap data structure is useful to merge many already-sorted input streams into a single sorted output stream
• Graph algorithms. By using heaps as internal traversal data structures, run time will be reduced by polynomial order. Examples of such problems are Prim's minimal spanning tree algorithm and Dijkstra's shortest path problem.

Full and almost full binary heaps may be represented in a very space-efficient way using an array alone. The first (or last) element will contain the root. The next two elements of the array contain its children. The next four contain the four children of the two child nodes, etc. Thus the children of the node at position n would be at positions 2n and 2n+1 in a one-based array, or 2n+1 and 2n+2 in a zero-based array. This allows moving up or down the tree by doing simple index computations. Balancing a heap is done by swapping elements which are out of order. As we can build a heap from an array without requiring extra memory (for the nodes, for example), heapsort can be used to sort an array in-place.

One more advantage of heaps over trees in some applications is that construction of heaps can be done in linear time using Tarjan's algorithm.