Heaps Flashcards
True or false, when we remove the min/max of a tree, we don’t need to maintain the completeness of the tree.
False. We need to find the new min and set that as the new root
The parent of a node at index i is at index ________ (using the floor that results from integer division).
(i - 1) // 2 (i.e. floor)
What is the five step process for removing a node
- Remember the value of the first element in the array (to be returned later). 2. Replace the value of the first element in the array with the value of the last element and remove the last element. 3. If the array is not empty (i.e., it started with more than one element), compute the indices of the children of the replacement element (2 * i + 1 and 2 * i + 2). ( If both of these elements fall beyond the bounds of the array, we can stop here.) 4. Compare the value of the replacement element with the minimum value of its two children (or possibly one child). 5. If the replacement element’s value is greater than its minimum child’s value, swap those two elements in the array, and repeat from step 3.
After we remove the min/max node from a heap, the we first replace that the root with _____
the last node. In an array, this is the last element.
We can efficiently IMPLEMENT the complete binary tree representation of a heap using a/an _______. Can any binary tree be represented using this?
array or dynamic array. Yes.
Whats the pseudocode while loop for percolating a node down for when you remove a node from the heap?
while priority > smallest child priority: swap with smallest child where priority is the new root node, and smallest child priority is the smallest child of that node
In a priority queue, whats the first element that gets dequeued?
The element with the highest priority
Whats the fundamental idea of the priority queue ADT
The priority queue is an ADT that associates a priority value with each element.
What happens if we use an array to implement a binary tree but the tree isn’t complete
If the binary tree isn’t complete, then the array will be less space efficient because there will be gaps in the array
What data structure is typically used to implement a priority queue?
A heap
Pseudocode for removing minimum value from an array based heap
- Remember the value of the first element in the array (to be returned later).
- Replace the value of the first element in the array with the value of the last element and remove the last element.
- If the array is not empty (i.e., it started with more than one element), compute the indices of the children of the replacement element (2 * i + 1 and 2 * i + 2).
- If both of these elements fall beyond the bounds of the array, we can stop here.
- Compare the value of the replacement element with the minimum value of its two children (or possibly one child).
- If the replacement element’s value is greater than its minimum child’s value, swap those two elements in the array, and repeat from step 3.
Does a heap maintain BST property where the left child is smaller and right child is bigger?
No. It just has to be a complete tree.
What are the two requirements for a minimizing heap data structure (or min heap)
Must be a COMPLETE binary tree EVERY NODE’S value must be less than or equal to the values of its children
In a min or max heap, which node is always the lowest or max value?
The root of the tree
Where is the lowest priority value located in a min heap?
The root node
What operation do you use for adding a node? Percolate down or up the tree?
Up
The _______ is an ADT that associates a priority value with each element. A ________ data structure is a complete binary tree in which every node’s value is less than or equal to the values of its children. A ___________ is typically implemented using a data structure called a ________.
priority queue min heap priority queue heap
Whats the n-step process for removing the root node from a heap?
- Remove the root node 2. Replace the root node with with whatever the last element in the heap 3. Fix the heap by percolating that node down
In an array-implemented heap, where is the last element and the “next open spot” in the heap
Last element is literally last element in the array, and next open spot is the index that follows after the last element in the array
Using an array to implement a binary tree that is not complete is bad because
It can leave big gaps in the array, wasting space.
When we add a new value to a min heap, we place it into the ________ and then percolate it ____ until its priority value is _____ than both of its children.
“next open spot”, up, less
True or false, in an array representation of a heap, the order of the nodes in the array follows the breadth first search results
True.
Pseudocode for inserting into an array based heap
- Put new element at the end of the array.
- Compute the inserted element’s parent index ((i - 1) / 2).
- Compare the value of the inserted element with the value of its parent.
- If the value of the parent is greater than the value of the inserted element, swap the elements in the array and repeat from step 2 else stop.
- Do not repeat if the element has reached the beginning of the array.
Whats the pseducode for percolating down the replacement node after removing the root node from a heap?
while priority > smallest child:
swap with smallest child
Which operation do you use for removing a node? Percolate down or up the tree?
Down
Whats the four step pseudocode process for inserting an element into the heap
- Put new element at the end of the array. 2. Find the index of the parent of the inserted element ((i - 1) / 2) 3. Compare the value of the inserted element with the value of its parent. 4. If the value of the parent is greater than the value of the inserted element, swap the elements in the array and repeat from step 2. Loop stops when #4 is false or the inserted element ends up at the beginning of the array
The last node at the deepest level in the heap is located where in the array?
The very last element of the array.
When removing a node from a MIN heap, what’s the node that gets removed?
Since the min heap is a tree, the root node is the lowest value in a min heap. The root node is the only node that ever gets removed in a min heap (and max heap)
A min (or max) heap is maintained through the addition and removal of nodes via ________, which move nodes up and down the tree according to their priority values.
percolations
In an array representation of a heap, the left and right children of a node at index i are stored at indices _________ and , respectively.
left: 2 * (i + 1), right: 2 * (i + 2)
Whats the pseudocode while loop for percolating a node up when you ADD a node to the heap
while new priority value < parent’s priority value: swap new node with parent
In an array representation of a heap, where is the root node stored?
Index 0
When we add a new value to a heap, we always first add it at the ____ which is located ______
“next open spot”, which is in the last level to the right of the furthest left node
