A Heap (Priority Queue) is a variation of binary trees with the addition of a heap property. This is useful for efficient retrieval of the highest (or lowest) priority element.

Ordered Data Structures Comparison

Set Data Structures Comparison

Advanced Topics

Heap Property

A Complete Binary Tree structure
1. It allows Array implementation. The left-to-right node insertion rule ensures that the tree remains compact and allows child-parent relationships to be calculated using simple index arithmetic.
2. It sustains the log n height
3. In a descendent (Min-Heap) or an ascendent (Max-Heap) order
4. Every parent node is smaller (larger) than or equal to its children. By maintaining this property, it can maintain O(log n) time complexity (traversing a side of the tree) instead of O(n) (traversing a all elements)
No Sorted Property: Unlike Binary Search Tree (BST), right node is might not larger than left node.

A size k of Min-Heap, the root represents the Kth largest element, because we always pop the smallest when heap is full, vice versa.

Example: [3, 2, 1, 5, 6, 4], k = 3

Push elements to 3 size minHeap:

Push 3
   3
-----------
Push 2
   2
  /
 3
-----------
Push 1
    1
   / \\
  3   2
-----------
Push 5
The heap is full, popping is required.
    2
   / \\
  3   5
-----------
Push 6
The heap is full, popping is required.
    3
   / \\
  5   6
-----------
Push 4
The heap is full, popping is required.
    4
   / \\
  5   6
  
Result: [4, 5, 6]

A size k of Min-Heap, the last node doesn’t mean the smallest number, because we always pop the smallest when heap is full, vice versa.

Parent / Child Index Formula

0-based Indexing

The root node is stored at index 0.
The last non-leaf node at index (length-2)/2.
The second last non-leaf node at index ((length-2)/2) - 1, the sibling of last non-leaf node.
The left child of the node at index i is at index 2i + 1.
The right child of the node at index i is at index 2i + 2.