Heap

A min-heap is a:

  • Complete binary tree

  • Value of the parent is always less than or equal to the value of its children

Representation

We can represent complete binary trees using arrays. We start the array at [0], so that when we add nodes that actually represent data then (i // 2) gives you the parent of node i. Imagine if we didn’t start the array at [0], then:

  0
 / \
1   2

1 // 2 = 0
2 // 2 = 1

But 1 and 2 have the same parent.

Now starting the array at [0]:

  1
 / \
2   3

2 // 2 = 1
3 // 2 = 1

Implementation

  • Use != 0 and not >= 0 in the while loops

  • For Insert, you percUp the last element, because you append the new element to the end. For Remove, you percDown the root, because you replace the root with the last element and then pop off the last element.

  • For heapify, start at the last parent and use percDown (https://stackoverflow.com/questions/13025163/why-siftdown-is-better-than-siftup-in-heapify). To remember: percDown parents (e.g. the root), while percUp children (e.g. the last element).

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

class Heap:

    def __init__(self):
        self.data = [0]
        self.size = 0

    def percUp(self, i):
        # != 0 and not >= 0
        while i // 2 != 0:
            # Be careful about the inequality
            # if child is less than parent,
            # then the child goes up the tree
            if self.data[i] < self.data[i // 2]:
                swap(self.data, i, i // 2)
            i = i // 2

    def minChild(self, i):
        left = 2*i
        if left > self.size:
            return -1
        right = left + 1
        if right > self.size:
            return left
        if self.data[left] < self.data[right]:
            return left
        return right

    def percDown(self, i):
        # moving down the tree means increasing i
        while i != self.size:
            mc = self.minChild(i)
            if mc == -1:
                break
            # Be careful about the inequality
            # if parent is greater than child
            # then the parent goes down the tree
            if self.data[i] > self.data[mc]:
                swap(self.data, i, mc)
            i = mc

    def insert(self, x):
        self.data.append(x)
        self.size += 1
        # percUp, not percDown
        # Be careful about the direction in the array and up and down.
        self.percUp(self.size)

    def removeMin(self):
        if self.size == 0:
            return
        m = self.data[1]
        self.data[1] = self.data[self.size]
        self.data.pop()
        self.size -= 1
        # percDown, not percUp
        # Be careful about the direction in the array and up and down.
        self.percDown(1)
        # Remember to return the min
        return m

    def buildHeap(self, arr):
        self.data = [0] + arr
        self.size = len(arr)
        # Start at the last parent.
        i = self.size // 2
        # != 0 and not >= 0
        while i != 0:
            self.percDown(i)
            i -= 1

def heap_sort(arr):
    heap = Heap()
    heap.buildHeap(arr)
    for i in range(len(arr)):
        arr[i] = heap.removeMin()
        
def test_heap_sort():
    arr = [1, 5, 3, -4, -10, 0]
    heap_sort(arr)
    assert arr == [-10, -4, 0, 1, 3, 5], arr
    
test_heap_sort()