Heap

Question 1

Use cases for a Max-Heap.

Answer 1

Priority Queue, e.g. OS task-scheduling, a OS update should be given a lower-priority than any other user started tasks and so shouldn’t run until they complete.

Question 2

A Priority Queue is an example use of a Max-Heap, what is a real-world analogy/example of a Max-Heap?

Answer 2

A hospital A+E ward. Triage will give patients a priority value based on their injuries/condition and those with the highest priority will be attended to first.

Question 3

Heap definition…

Answer 3

A special tree in which each level contains Node’s with values more extreme (greater than or less than), the Nodes on the level above it.
Each available node is filled left to right.

Question 4

What does a Min-Heap do?

Answer 4

It ensures that the node with the LOWEST value is always at the top of the tree.

Question 5

What does a Max-Heap do?

Answer 5

It ensures that the node with the HIGHEST values is always at the top of the tree.

Question 6

Max/Min-Heap’s two defining properties?

Answer 6

1. The value at the Root Node must be
   the MAXIMUM || MINIMUM amongst all of its children.
2. This fact must be the same recursively for all parent Nodes contained within the Heap.

Question 7

How do we ADD an element to a Heap?

Answer 7

1. Add the node to the most Bottom-Left position available. If a hierarchy-level has free space then it goes to the left-most free spot on that level. If not, then it will go down to a new level from the left-most leaf.
2. Recursively go up the tree and swap Nodes if necessary. Max-Heap: If larger then parent, then swap. Min-Heap: If smaller than parent then swap.

Question 8

How do we DELETE an element from a Heap? (3)

Answer 8

1. Remove the root node from our heap. You will likely return this value to the caller.
2. Replace it with the Node furthest to the bottom-right.
3. “Heapify” the Heap by comparing parent Node’s to their children and swapping if necessary.

Question 9

What is “Heapifying”?

Answer 9

It fixes the heap to ensure the max/min value is always at the root. You compare the Root Node to its children and swap if necessary. Repeat through all parent nodes in the tree.

Question 10

What sorting algorithm uses a Heap?

Answer 10

The Heap Sort.

Question 11

How does a Heap Sort work?

Answer 11

It takes all the values to be sorted and builds a Heap Tree. It then takes the Root Node’s value and adds it to its sorted list.

It then “heapify’s” the tree to ensure the Highest/Lowest value is at the Root Node and repeats until the Tree is empty.

Question 12

What is the Big(O) of ACCESS a heap?

Answer 12

O(1). Simply getting the Root Node.

Question 13

What is the Big(O) of RE-BALANCING “Heapifying” a heap?

Answer 13

O(log n). Why?

Question 14

What is a binary-heap?

Answer 14

A (maximum) heap is a complete binary tree having a key associated with each node, the key of each parent node being greater than or equal to the keys of its child nodes

Question 15

What two operations does the heap ADT support?

Answer 15

insert new element and delete/retrieve maximum element

These both can be performed in O(log n) time.

Question 16

What is the most common way to represent a heap?

Answer 16

Flattened into an array
The left child is stored at 2n + 1
The right child is stored at 2n + 2

Question 17

What is a priority queue?

Answer 17

A priority queue is a container for a totally-ordered set of elements (ADT)

Question 18

What operations does a priority queue support?

Answer 18

insert, peek front, delete front, decrease key (i.e. priority of an element)

Question 19

How is priority queue often implemented

Answer 19

Frequently is implemented using a binary heap data structure

Question 20

How do you create a selection algorithm that runs in Θ(n) for all input?

Answer 20

ensure that “good” pivots are found: median-of-medians linear-time algorithm

The divide-and-conquer recursive M.-M. algorithm:
1. 1 Partition input of n items into groups of five items.
2. Find exact median of each of the 5-element groups.
3. Find the median of these dn/5e medians (by recursion) as selected pivot.