Skip to content

heap.md

Latest commit

 

History

History
143 lines (99 loc) · 6.08 KB

heap.md

File metadata and controls

143 lines (99 loc) · 6.08 KB
Raw

Heap

  1. Max Heap
  2. Min Heap

Max Heap

Description

[Medium] A binary heap or heap is a partially ordered binary tree which satisfies the heap property. The heap property specifies a relationship between parent and child nodes. You may have a max heap, in which all parent nodes are greater than or equal to their child nodes, or a min heap, in which the reverse is true. Binary heaps are also complete binary trees. This means that all levels of the tree are fully filled and if the last level is partially filled it is filled from left to right.

While binary heaps may be implemented as tree structures with nodes that contain left and right references, the partial ordering according to the heap property allows us to represent the heap with an array. The parent-children relationship is what we're interested in and with simple arithmetic we can compute the children of any parent and the parent of any child node. The relationship can be represented as:

For any element at index of i:

  • Its left child is at the index of 2 * i + 1
  • Its right child at the index of 2 * i + 2
  • Its parent node is at the index of Math.floor((i - 1) / 2)

For instance, consider this array representation of a binary max heap:

[90, 85, 80, 70, 60, 75, 65, 50, 55, 45]

To represent it as a binary tree is like this:

                90
              /    \
            85      80
           /  \    /  \
         70    60  75  65
        /  \   /
      50   55 45

In this binary tree, the value of each node is bigger than its children nodes.

Implement max heap data structure and its relevant methods:

  • insert() Add an element to the heap. When doing insertion, always make sure every node should be greater than their children. To achieve that, here's the approach that is taken:

    1. Add the new element to the end of the array.
    2. If the element is larger than its parent, switch them.
    3. Continue switching until the new element is either smaller than its parent or it reaches the root of the tree.

    For example, in the above heap, insert 86:

    1. Append 81 to the end of array: [90, 85, 80, 70, 60, 75, 65, 50, 55, 45, 86]
    2. Its index is i = 10; its parent node index is Math.floor((i - 1) / 2) = 4; therefore a[4] = 60
    3. Because 86 > 60, swap them: [90, 85, 80, 70, 86, 75, 65, 50, 55, 45, 60]
    4. Now its index becomes 4; its parent node index is Math.floor((i - 1) / 2) = 1; a[1] = 85.
    5. Because 86 > 85, swap them: [90, 86, 80, 70, 85, 75, 65, 50, 55, 45, 60]
    6. Now its index becomes 1; its parent node index is Math.floor((i - 1) / 2) = 0; a[0] = 90.
    7. Becasue 86 < 90, so we just stop here. And its tree representation after the insertion looks like:
                  90
            /    \
          86      80
         /  \    /  \
       70    85  75  65
      /  \   / \
    50   55 45 60

    Time complexity for insertion is O(log n) in the worst case because it possibly goes through every level from the bottom to top of the tree.

  • getMax() Get the max value of max heap. This is a straight forward operation - as per the definition of max heap, its max value is always the first value (the root value of the tree).

  • extractMax() Remove and return the max value of heap.

  1. Replace the first element with the last one: [45, 85, 80, 70, 60, 75, 65, 50, 55]

  2. Move 45 to its correct place by heapifying the root node: heapify(0)

  • heapify(i) Heapify a subtree with the root at a given index. This operation assumes that all the oher nodes, except the node of the given index satisfy heap property. For example: [90, 10, 80, 70, 60, 75, 65, 50, 55, 45], its tree structure:
                90
              /    \
            10      80
           /  \    /  \
         70    60  75  65
        /  \   /
      50   55 45

We are going do heapify(1) - whose value is 10, doesn't satisfy the heap property.

  1. i = 1 so its left child index is l = 2 * i + 1 = 2, whose value is 70; right child index r = 2*i + 2 = 3, whose value is 60. The largest one is 70 (at index 3, not the root node), so swap 70 and 10: [90, 70, 80, 10, 60, 75, 65, 50, 55, 45]
  2. Now number 10 is at index 3. We are doing heapify(3): i = 3, its left child index is l = 2 * i + 1 = 7, whose value is 50; right child index is r = 2 * i + 2 = 8, whose value is 55. The largest one is 55 at index of 8, not the root node, so swap 10 and 55: [90, 70, 80, 50, 60, 75, 65, 10, 55, 45]
  3. Now number 10 is at index 7. We are doing heapify(7): i = 7, its left child index is l = 2 * i + 1 = 15, no child node; right child index is r = 2 * i + 2 = 16, no child node. So the heapify stops here and its final heap is [90, 70, 80, 50, 60, 75, 65, 10, 55, 45] and its tree structure is:
                90
              /    \
            70      80
           /  \    /  \
         55    60  75  65
        /  \   /
      50   10 45

Time complexity for heapify is also O(log n) in the worst case because it possibly goes through every level from the top to tottom of the tree.

Notes

  • Heap data structure is commonly used in priority queues and sorting.
  • It has good time complexity and space complexity(represented as an array).
  • It is not ideal for searching. Searching for an element in a heap requires traversing the entire tree, which has a time complexity of O(n).

Implementation

Back to index

Min Heap

Description

[Medium] Min heap has the exact same principle as max heap just its root node is the smallest value and every node is smaller than its children.

Implementation

Back to index