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
