Heaps Flashcards
A ______________ is a special queue where the key with the highest priority is found at one end.
Priority Queue
These are used to schedule jobs on a computer shared among multiple uses.
Priority Queue
The ______ indicate the priority.
Key
The _________ data structure is an array that we can view as a nearly complete binary tree.
(Binary) Heap
True or False:
In a Heap, the tree is always full on all levels.
FALSE. It can possibly be not full at the bottom most level.
TRUE OR FALSE:
A heap is filled from left to right
True
In a heap represented by an array, the root of the tree is stored at which index.
1
For any node at index n, its parent is at index?
n//2
For any node at index n, its left child is at index?
2n
For any node at index n, its right child is at index?
2n + 1
For every node other than the root, the value of a node is at most the value of its parent.
max-heap
The __________ in a max heap is at the root.
largest value
For every node other than the root, the value of a node is at least the value of its parent.
min-heap
The __________ in a min heap is at the root.
smallest value
Synonyms are sift-up, float up, min-heapify
percolate up
To delete in a heap:
1) Swap root with last key
2) Update heap size
3) Fix up from the root (percolate down)
How to build a heap given an array,
Starting from index i/2 (i is size of array) to 1, percolate down.
Run times for using a heap for a priority queue
insert O(log n)
delete min/max - O(log n)
build-heap - O(n)
A sorting algorithm that call build-max-heap, then performs n-1 delete-max operations
Heap Sort
What is the running time of heap sort:
Hint: build-heap O(n)
n-1 delete O(n log n)
O(n log n)
