Searching and Sorting II

Question 1

What is a queue ?

Answer 1

First in First Out

Question 2

What is a Priority Queue ?

Answer 2

Each element has a priority,
Dequeue removes the highest priority item, not the oldest,
if priorities match, normal fifo

Question 3

What is a heap ?

Answer 3

A complete binary tree represented as an array,
Max-heap - Every parent node is greater than or equal to its children,
Min-heap - Every parent node is less than or euqal to its children.

Question 4

What are the steps of a HeapSort algorithm ?

Answer 4

1. Build a max heap from the array,
2. Swap the root (largest) with the last element,
3. Reduce the heap size and call Max_Heapify on the root,
4. repeat until the array is sorted.