Heap Demo



 




A heap is a data structure designed to efficiently maintain a list that always returns the first item in a sort order very quickly - O(1). While a heap looks and behaves (mostly) like a tree, it can easily be kept in an array or indexable list. (view the “Logic” section of the source of this page for more)

Given an arbitrary list, it must be heapified before this will work, as you may demonstrate by clicking the Heapify button above. You can reset the list by clicking Generate. To make the heapify more visible, the data generation on this page starts either with the list in reverse order (count down), or random. If the list is already sorted, heapify has nothing to do!

Heapify signifies the process of enforcing a very simple rule:

If that rule is broken, the parent nodes and child nodes are swapped until the ordering is valid for all nodes.

The design can be to return either the minimum or maximum element quickly. The principles are identical. The above demonstrates a Minimum Heap

Because the binary (balanced) tree is actually kept in an array, all the rows must be complete except the bottom row, which must always be complete from the left. In other words, it's a complete binary tree. Therefore, insertions go to the end of the array and are bubbled up. Likewise, deletion of the first element is accomplished by swapping the first and last elements, shortening the array by one, and bubbling the first element down.

The insertion or deletion time is (O(log2(n))) because the structure behaves as a binary tree and the most one needs to traverse for either operation is the height of the tree.

In Java, this structure is called a PriorityQueue. Python has a native library called heapq, which manages a list as a heap.

A typical usage is for merging multiple streams.

For more on heaps and heap sort, see https://www.geeksforgeeks.org/heap-sort/