heaps

Question 1

Priority Queue ADT

Answer 1

Priority Queue is an extension of queue with following properties:
* Entries consist of key (priority) and value.
* Entries in priority queue are ordered by key
* An entry with high key is dequeued before an element with low key.
* If two entries have the same key, they are served according to their order in the queue.

Question 2

Priority Queue operations

Answer 2

A typical priority queue supports following operations:
* insert(key, value): Inserts an item with given key.
* min/max(): Returns the smallest/largest key item.
* removemin/removemax(): Removes the smallest/largest key item.

Question 3

heap property

Answer 3

if 𝑃 is a parent node of 𝐶, then the key of 𝑃 is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of 𝐶.

Question 4

max heap

Answer 4

A max heap is a heap such that for each node except the root, the parent of node 𝑖 is greater than or equal to node 𝑖 (max-heap property)

Question 5

Heap as a Tree

Answer 5

root of tree: first element in the array, corresponding to 𝑖=1
parent(𝑖)=𝑖/2: returns the index of node’s parent
left(𝑖)=2𝑖: returns the index of node’s left child
right(𝑖)=2𝑖+1: returns the index of node’s right child

all these cost O(1)

Question 6

max heap operations

Answer 6

max: return the maximum item
extract_max: return and remove the maximum item
build_max_heap: produce a max-heap from an unordered array
max_heapify: correct a single violation of the heap property in a subtree at its root
insert
heapsort

Question 7

max heapify pseudocode

Answer 7

max_heapify(A, i):
l = left(i)
r = right(i)

if (l <= heap-size(A) and A[l] > A[i])
then largest = l else largest = i
if (r <= heap-size(A) and A[r] > A[largest])
then largest = r

if largest != i
then exchange A[i] and A[largest]
max_heapify(A, largest)

Question 8

build_max_heap(A)

Answer 8

build_max_heap(A):
for i=n/2 down to 1
do max_heapify(A, i)

Time=O(n) where n is number of elements in the array

Question 9

Heapsort Sorting Strategy

Answer 9

Build Max Heap from unordered array;
Find maximum element 𝐴[1];
Swap elements 𝐴[𝑛] and 𝐴[1]: now max element is at the end of the array!
Discard node 𝑛 from heap (by decrementing heap-size variable)
New root may violate max heap property, but its children are max heaps. Run max_heapify to fix this.
Go to Step 2 unless heap is empty.

Question 10

Heapsort Running time

Answer 10

after 𝑛 iterations the Heap is empty
every iteration involves a swap and a max_heapify operation;
hence it takes 𝑂(𝑛 log⁡𝑛) time overall