# Heap Flashcards

1
Q

Use cases for a Max-Heap.

A

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.

2
Q

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

A

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.

3
Q

Heap definition…

A

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.

4
Q

What does a Min-Heap do?

A

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

5
Q

What does a Max-Heap do?

A

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

6
Q

Max/Min-Heap’s two defining properties?

A
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.
7
Q

How do we ADD an element to a Heap?

A
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.
8
Q

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

A
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.
9
Q

What is “Heapifying”?

A

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.

10
Q

What sorting algorithm uses a Heap?

A

The Heap Sort.

11
Q

How does a Heap Sort work?

A

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.

12
Q

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

A

O(1). Simply getting the Root Node.

13
Q

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

A

O(log n). Why?

14
Q

What is a binary-heap?

A

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

15
Q

What two operations does the heap ADT support?

A

insert new element and delete/retrieve maximum element

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

16
Q

What is the most common way to represent a heap?

A

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

17
Q

What is a priority queue?

A

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

18
Q

What operations does a priority queue support?

A

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

19
Q

How is priority queue often implemented

A

Frequently is implemented using a binary heap data structure

20
Q

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

A

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.