Binary Heap theory


What is Binary Heap

  • Definition : Binary Heap is a Binary Tree with some special properties.


    1. Heap property

      • Value of any given node must be <= value of its children(Min-Heap)
      • Value of any given node must be >= value of its children(Max-Heap)

    2. Complete tree

      • All levels are completely filled except possibly the last level and the last level has all keys as left as possible.
      • This makes Binary Heap ideal candidate for Array Implementation.

Why should we learn Binary Heap?

There are cases when we want to find ‘min/max’ number among set of numbers in log(n) time. Also, we want to make sure that Inserting additional numbers does not take more than O(log n) time.


  • Possible Solutions:

    1. Store the numbers in sorted Array <- Take O(n) time complexity
    2. Store the numbers in Linked List in sorted manner <- Take O(n) time complexity

Binary Heap will solve this problem with O(log n).

Types of Binary Heap

  1. Min-Heap : If the value of each node is less than or equal to value of both of its children.
  2. Max-Heap : If the value of each node is more than or equal to value of both of its children.

Practical Use

  1. Prim’s Algorithm
  2. Heap Sort
  3. Priority Queue



Binary Heap - Array Representaion

  • Implementation options
    • Array based Implementation
    • Reference/Pointer based Implementation

Insertion in Heap

1
2
3
4
5
6
7
insertValueInHeap(value)
  if tree does not exists
    return error message
  else
    insert 'value' in first unused cell of Array
    sizeOfHeap++
    heapifyBottomToTop(sizeOfHeap)  ----- O(log n) : this means the height of the tree, the recursive call will step every node until it reaches the number which is smaller(Min-Heap) than its children

  • Time Complexity - O(log n)
  • Space Complexity - O(log n)

ExtractMin from Heap

1
2
3
4
5
6
7
8
extractMin()
  if tree does not exist
    return error message
  else
    extract 1st cell of Array
    promote last element to first
    sizeOfHeap--
    heapifyTopToBottom(1)

  • Time Complexity - O(log n)
  • Space Complexity - O(log n)

Delete Heap


1
2
deleteHeap()
  set array to null

  • Time Complexity - O(1)
  • Space Complexity - O(1)

Reason why we don’t use Reference implementation(linked list) on Binary Heap

  • When we try to extract min/max number from the tree using reference, we need to loop all over the tree to find the value. This procedure takes O(n) time complexity. Inefficient!!



출처 : “Data Structures & Algorithms” by DS GUY