Min or Max Heap


#heap
- 3 minutes read - 479 words

Notebook

Heap

Heap is a binary tree data structure in which the root is either the smallest or the largest element of the elements in the tree.

  • Heap acts as a priority queue and as you remove the root element (top priority) the next root becomes the next prioritized element.
  • Heap is stored as an array where for the ith element the left child is 2i+1 and right child is 2i+2
heap = []

For this discussion I’ll be using min-heap.

Push

A new element is added to the heap by appending it to the array and then moving the element upwards until the top element (0th index) is again the smallest.

element = 1
heap.append(element)
siftup(heap)

Pop

The top element is popped whenever there is a need for the smallest element among the set of elements that got pushed into the heap. To do that the top element is returned and overwritten by the last element of the heap array. The heap array size is then reduced by one and the element is moved downwards until the heap properties are reinstated.

top = heap[0]
heap[0] = heap[-1]
heap.pop(-1)
siftdown(heap)

siftup

def siftup(heap):
    # last element is the child index
    c = len(heap)-1
    # get the parent index based on
    # i -> 2i+1, 2i+2 parent-child rule
    p = (c - 1) // 2
    # while parent index is valid
    while p >= 0:
        # compare parent and child element
        if heap[p] > heap[c]:
            # if parent is bigger than swap
            # of sift up the smaller element
            heap[p], heap[c] = heap[c], heap[p]
        # in any case, parent is the new child
        c = p
        # get the new parent
        p = (c-1) // 2

siftdown

def siftdown(heap):
    # start from the top, sifting down
    # parent index is 0
    p = 0
    # while parent index is valid
    while p < len(heap):
        # get the left child 2i+1
        l = 2*p + 1
        # get the right child 2i+2
        r = 2*p + 2
        # find the smallest index among three
        # parent, left child, right child
        smallest = p
        if l < len(heap) and heap[l] < heap[smallest]:
            smallest = l
        if r < len(heap) and heap[r] < heap[smallest]:
            smallest = r
        # if the smallest index is not the parent
        if smallest != p:
            # swap the parent with smallest children
            heap[p], heap[smallest] = heap[smallest], heap[p]
            # smallest index is the new parent
            # keep sifting down
            p = smallest
        else:
            # done the parent is in the right position
            # cannot sift down more
            break

run

nums = [2,3,5,1,5,6,0,10]
for n in nums:
    heap.append(n)
    siftup(heap)

print(heap[0])
heap[0] = heap[-1]
heap.pop(-1)
siftdown(heap)
print(heap[0])

Python Heap Library

doc

import heapq

nums = [2,3,5,1,5,6,0,10]

# min heap
h = []
for n in nums:
    heapq.heappush(h, n)
print(heapq.heappop(h))
print(heapq.heappop(h))

# max-heap (kind-of)
print(heapq.nlargest(len(nums), nums)[0])
# alternate min-heap
print(heapq.nsmallest(len(nums), nums)[0])