Max Heap Test¶

In [18]:

import math

In [21]:

heap = [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]

*n.b. this is 3-level tree (misread my notes).

Here are illustrations.

Parent floor(i/2)¶

In [23]:

def parent(aheap, i):
    if i == 0: return None
    #return floor(i/2)

In [25]:

def test_root_parent():
    assert(parent(heap, 0) is None)
    print("pass")

test_root_parent()

pass

In [5]:

def test_a_parent():
    assert(False)

test_a_parent()

Left (2i)¶

In [6]:

#def left(i):
    #return 2i

In [7]:

def test_a_left():
    left(i)

Right (2i + 1)¶

In [8]:

#def right(i):
    #return 2i + 1

In [9]:

def test_a_right():
    assert(False)

Insert (Push)¶

{percolate, bubble, sift, trickle, heapify, cascade} up

1. Add element to the bottom level¶

2. Compare with parent¶

3. If e > p –> swap else: stop¶

In [10]:

def test_push():
    n = 11
    assert(False)

Extract (Pop)¶

{percolate, bubble, sift, trickle, heapify, cascade} down

1. Replace the root with last e¶

2. Compare with child¶

3. If root < c swap else: stop¶

In [11]:

def test_pop():
    assert(False)

Heapify¶

max-heapify(A,i): lft = left(i) r = right(i) if l<= size(A) and A[lft] > A[i]: largest = lft else largest = i if r <= size(A) and A[r] > A[largest] largest = r if largest <> i: exchange A[i] with A[largest] max-heapify(A,largest)

In [ ]:

def test_heapify(A, i):
    assert(False)