DATA STRUCTURES HEAPS EXAM
QUESTIONS AND ANSWERS
max-heap - Correct Answers -A binary tree that maintains the simple property that a
node's key is greater than or equal to the node's children's keys
A max-heap's root must have the maximum key.
Max-heap insert - Correct Answers -An insert into a max-heap starts by inserting the
node in the tree's last level, and then swapping the node with its parent until no max-
heap property violation occurs. Inserts fill a level (left-to-right) before adding another
level, so the tree's height is always the minimum possible. The upward movement of a
node in a max-heap is sometime called percolating.
Max-heap remove - Correct Answers -A remove from a max-heap is always a removal
of the root, and is done by replacing the root with the last level's last node, and
swapping that node with its greatest child until no max-heap property violation occurs.
Because upon completion that node will occupy another node's location (which was
swapped upwards), the tree height remains the minimum possible.
Given N nodes, what is the height of a max-heap? - Correct Answers -logN
what is the worst-case complexity of an insert,
complexity for removing root - Correct Answers -o(logN)
min-heap - Correct Answers -A min-heap is similar to a max-heap, but a node's key is
less than or equal to its children's keys.
Online tech support waiting lines
low # = top priority
Heap storage - Correct Answers -Heaps are typically stored using arrays. Given a tree
representation of a heap, the heap's array form is produced by traversing the tree's
levels from left to right and top to bottom. The root node is always the entry at index 0 in
the array, the root's left child is the entry at index 1, the root's right child is the entry at
index 2, and so on.
heap parent index formula - Correct Answers -floor((i - 1) / 2)
QUESTIONS AND ANSWERS
max-heap - Correct Answers -A binary tree that maintains the simple property that a
node's key is greater than or equal to the node's children's keys
A max-heap's root must have the maximum key.
Max-heap insert - Correct Answers -An insert into a max-heap starts by inserting the
node in the tree's last level, and then swapping the node with its parent until no max-
heap property violation occurs. Inserts fill a level (left-to-right) before adding another
level, so the tree's height is always the minimum possible. The upward movement of a
node in a max-heap is sometime called percolating.
Max-heap remove - Correct Answers -A remove from a max-heap is always a removal
of the root, and is done by replacing the root with the last level's last node, and
swapping that node with its greatest child until no max-heap property violation occurs.
Because upon completion that node will occupy another node's location (which was
swapped upwards), the tree height remains the minimum possible.
Given N nodes, what is the height of a max-heap? - Correct Answers -logN
what is the worst-case complexity of an insert,
complexity for removing root - Correct Answers -o(logN)
min-heap - Correct Answers -A min-heap is similar to a max-heap, but a node's key is
less than or equal to its children's keys.
Online tech support waiting lines
low # = top priority
Heap storage - Correct Answers -Heaps are typically stored using arrays. Given a tree
representation of a heap, the heap's array form is produced by traversing the tree's
levels from left to right and top to bottom. The root node is always the entry at index 0 in
the array, the root's left child is the entry at index 1, the root's right child is the entry at
index 2, and so on.
heap parent index formula - Correct Answers -floor((i - 1) / 2)
