Common problems that uses Heap data structure:

Apply Heap data structure to

1. top K elements.

   1. Heap is good to find the top K elements with smaller than O(n log n) time.

   2. O( n log K) is the Time complexity.

2. Because it's good for maintaining knowledge on past biggest or smallest numbers. And find a ranked one within that

Conceptual Review

Priority Queue is implemented with a heap data structure.

Common operations:

insert(x, S)

max(S)

extract_max(S), return and remove max from S

increase_key(S, x, k)

Heap:

Array structure. But can be visualize as a nearly complete binary tree

• root: index 1, first element
• parent(i): i/2
• left(i): 2i
• right(i): 2i + 1

Heap type and its invariant

Max heap: key of the node is larger than keys of its children

Min heap

Note, this is a strong assumption to make and a lot of operations are based on it

Heap Operations:

1. build_max_heap: O(n) for backward building: meaning array already exists.
2. max_heapify: O( log n) because the height is log n

Heap Sort Algorithm:

1. build max heap
2. find max elem, A[1]
3. exchange A[1] with A[n]
4. decrement heap size to n-1
5. max_heapify(A, 1) to preserve the max heap property
6. repeat from step 2