# 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])