Binary heap

Binary heap is a tree-like data structure that generally can be separated into two types: min-heap and max-heap. The difference is that in the max-heap all nodes are greater than or equal to each of it’s children. In the min-heap everything is vise versa, all nodes are less than or equal to each of its children. Thus, the highest (max-heap) or lowest (min-heap) element is always on the top and this is the main advantage which provides possibility to access the min or the max element in constant time. Another important property is that all levels, except the last last one, must be full.

heap

The last level can be either full or not, but all new elements always added to the last level, from the left to the right.

Due to its advantages, the heap has many applications, for instance, Dijkstra’s shortest-path algorithm, heapsort or priority queue.

Implementation

The most common and effective way to implement heap which doesn’t consume a lot of memory is indexed array.

array_heap

 

In array based heap, the root element is placed in M[0] (where M is an array, N is a length of the array and is an index of the array with possible values: {i ∈ Z,0 ≤ i < N}), it’s children placed at indices 2i + 1 and 2i + 2. Parent can be accessed by index floor((i – 1) / 2).

The most common operations on heap are following:

  1. Create heap – creates a new, empty binary heap.
  2. Heapify – creates a new heap from given array of elements.
  3. Insert – adds a new element into a heap.
  4. Find max – returns maximum element of a heap. In case of min-heap the operation is called “Find min” and returns the minimum element.
  5. Delete max – returns maximum element of a heap, removing the item from the heap. In case of min-heap the operation is called “Delete min” and returns the minimum element, removing the element from the heap.
  6. Is empty – checks whether a heap is empty.
  7. Size – returns the number of elements in a heap.

The below code snippet is a simple implementation of the max-heap in java:

https://github.com/alexvolov/algorithms-and-data-structures/blob/master/src/main/java/com/alexvolov/ads/ds/impl/BinaryHeap.java

The algorithm of the insert operation is pretty straightforward:

  1. Insert a new element of the heap into the last vacant space in array.
  2. Compare new element with it’s parent, if they are in correct order go to the point 4, otherwise point 3.
  3. Replace parent with the new element and go to the step 2.
  4. End.

The algorithm of the delete operation is following:

  1. Swap the last element in the heap with the  first element.
  2. Compare first element with it’s children, if they are in correct order go to step 4, otherwise to step 3.
  3. Swap element with the largest child, and go to the point 2.
  4. End.
Complexity

Both insert and delete operations have O(log n) time complexity in average and worst case. Getting max/min element has constant time complexity in all cases.

Leave a Reply