Problem 6.1

Building a heap using insertion

We can build a heap by repeatedly calling MAX-HEAP-INSERT to insert the elements into the heap. Consider the following variation of the BUILD-MAX-HEAP procedure.

BUILD-MAX-HEAP'(A)
  A.heap-size = 1
  for i = 2 to A.length
      MAX-HEAP-INSERT(A, A[i])
  1. Do the procedures BUILD-MAX-HEAP and BUILD-MAX-HEAP' always create the same heap when run on the same input array? Prove that they do, or provide a counterexample.
  2. Show that in the worst case, BUILD-MAX-HEAP' requires $\Theta(n\lg{n})$ time to build a $n$-element heap.

Same heaps?

No. They produce different heaps. This is illustrated with $\langle 1, 2, 3, 4, 5, 6 \rangle$. Results are shown below.

Complexity

MAX-HEAP-INSERT is a $\Theta(\lg{n})$ operation in the worst case and it gets called $n - 1$ times. MAX-HEAP-INSERT might need to pull each element up to the beginning of the heap, that is, $\lg{k}$ operations whatever $k$ currently is. The worst case happens when the array is sorted. Thus the complexity is:

$$ \sum_{i=2}^{n}\lg{i} = \lg(n!) = \Theta(n\lg{n})$$

The above is due to exercise 3.2.3.

Python runner output

Heap builds for: 1, 2, 3, 4, 5, 6
---------------------------------
BUILD-MAX-HEAP:  6, 5, 3, 4, 2, 1
BUILD-MAX-HEAP': 6, 4, 5, 1, 3, 2

Python code

##############################################################################
# DATA STRUCTURES
##############################################################################

class heap:
    def __init__(self, items, size = None):
        self.items = items
        self.heap_size = size or len(items)

    def __getitem__(self, key):
        return self.items[key]

    def __setitem__(self, key, value):
        self.items[key] = value

    def __len__(self):
        return len(self.items)

def left(i):
    return 2 * i + 1

def right(i):
    return 2 * i + 2

def parent(i):
    return (i - 1) // 2

##############################################################################
# Standard BUILD-MAX-HEAP
##############################################################################

def max_heapify(A, i):
    l = left(i)
    r = right(i)
    if l < A.heap_size and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r < A.heap_size and A[r] > A[largest]:
        largest = r

    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        max_heapify(A, largest)

def build_max_heap(A):
    A.heap_size = len(A)
    for i in range(len(A) // 2, -1, -1):
        max_heapify(A, i)

##############################################################################
# Exercise BUILD-MAX-HEAP'
##############################################################################

def heap_increase_key(A, i, key):
    if key < A[i]:
        raise Exception("new key is smaller than current key")
    A[i] = key
    while i > 0 and A[parent(i)] < A[i]:
        A[i], A[parent(i)] = A[parent(i)], A[i]
        i = parent(i)

def max_heap_insert(A, key):
    A.heap_size += 1
    A[A.heap_size - 1] = float("-inf")
    heap_increase_key(A, A.heap_size - 1, key)

def build_max_heap2(A):
    A.heap_size = 1
    for i in range(1, len(A)):
        max_heap_insert(A, A[i])