Heaps and Treaps - Chapter 7 Flashcards
A blank is a complete binary tree that maintains the simple property that a node’s key is greater than or equal to the node’s children’s keys.
max-heap
a max-heap’s blank always has the maximum key in the entire tree.
root
An blank 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.
insert
The upward movement of a node in a max-heap is called blank.
percolating
A blank 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
remove
what is the height of a max-heap?
floor(logN)
Given a max-heap with N nodes, what is the worst-case complexity of an insert, assuming an insert is dominated by the swaps?
O(logN)
Given a max-heap with levels 0, 1, 2, and 3, with the last level not full, after inserting a new node, what is the maximum possible swaps needed?
3
Given a max-heap with N nodes, what is the complexity for removing the root?
O(logN)
A blank is similar to a max-heap, but a node’s key is less than or equal to its children’s keys.
min-heap
A customer with a higher priority has a blank numerical value in the min-heap.
lower
Heaps are typically stored using blank. 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.
arrays
Because heaps are not implemented with node structures and parent/child pointers, traversing from a node to parent or child nodes requires referring to nodes by blank.
index
Node index 0 Parent index ? Child indices ?
None
1,2
Node index 1 Parent index ? Child indices ??
0
3,4
Node index 2 Parent index ? Child indices ?
0
5,6
Node index 3 Parent index ? Child indices ?
1
7,8
Node index 4 Parent index? Child indices?
1
9, 10
Node index 5 Parent index ? Child indices??
2
11, 12
Node index i Parent index ? Child indices??
floor((i-1)/2)
2 * i +1, 2* i + 2
MaxHeapPercolateUp(nodeIndex, heapArray) {
while (nodeIndex > 0) {
parentIndex = (nodeIndex - 1) / 2
if (heapArray[nodeIndex] <= heapArray[parentIndex])
return
else {
swap heapArray[nodeIndex] and heapArray[parentIndex]
nodeIndex = parentIndex
}
}
}
Max-heap percolate up algorithm.
MaxHeapPercolateDown(nodeIndex, heapArray, arraySize) {
childIndex = 2 * nodeIndex + 1
value = heapArray[nodeIndex]
while (childIndex < arraySize) {
// Find the max among the node and all the node’s children
maxValue = value
maxIndex = -1
for (i = 0; i < 2 && i + childIndex < arraySize; i++) {
if (heapArray[i + childIndex] > maxValue) {
maxValue = heapArray[i + childIndex]
maxIndex = i + childIndex
}
}
if (maxValue == value) {
return
}
else {
swap heapArray[nodeIndex] and heapArray[maxIndex]
nodeIndex = maxIndex
childIndex = 2 * nodeIndex + 1
} } }
Max-heap percolate down algorithm.
blank = (node_index - 1) // 2
parent_index
blank = 2 * node_index + 1
left_child_index
blank = 2 * node_index + 2
right_child_index
The MaxHeap methods blank and blank make use of two methods, percolate_up() and percolate_down().
insert() and remove()
blank takes a starting index (node_index) as an argument and compares the value at node_index (the current value) to the parent value. If the parent value is smaller than the current value, the two items swap positions in the list. The process then repeats from the current value’s new position. The algorithm stops when the current value reaches the root (at index 0), or when the parent value is greater than or equal to the current value, meaning no max heap violations exist in the list.
percolate_up()
The blank method takes a starting index as an argument and compares the value at node_index (the current value) to the current value’s two children’s values. If either child’s value is larger than the current value, the current value swaps positions with whichever child is larger. The process continues from the current value’s new position. The algorithm ends when the current value is at the tree’s bottom level, or when both children’s values are less than or equal to the current value, meaning no max heap violations exist in the list.
percolate_down()
The MaxHeap blank adds a new value to the end of the list, and then uses the percolate_up() method to restore the max heap property.
insert() method
The MaxHeap blank has no parameters and returns the maximum value in the list (which always occurs at index 0). The list’s index 0 position is assigned with the last item in the list, and the last item is removed using the list’s pop() method. The max heap property is restored by calling percolate_down() from the index 0 position.
remove() method
Blank is a sorting algorithm that takes advantage of a max-heap’s properties by repeatedly removing the max and building a sorted array in reverse order.
Heapsort
An array of unsorted values must first be converted into a heap. The blank operation is used to turn an array into a heap.
heapify
Since leaf nodes already satisfy the max heap property, heapifying to build a max-heap is achieved by blank on every non-leaf node in reverse order.
percolating down
The heapify operation starts on the internal node with the largest index and continues down to, and including, the root node at index 0. Given a binary tree with N nodes, the largest internal node index is blank
floor(N/2) - 1
Heapsort begins by heapifying the array into a max-heap and initializing an end index value to the size of the array minus 1. Heapsort repeatedly removes the maximum value, stores that value at the end index, and decrements the end index. The removal loop repeats until the end index is blank.
0
Heapsort uses blank to sort an array. The first loop heapifies the array using MaxHeapPercolateDown. The second loop removes the maximum value, stores that value at the end index, and decrements the end index, until the end index is 0.
2 loops
The heap sort algorithm can be implemented in Python to sort a list in place. Only the blank function is needed, not a full heap implementation.
percolate down
The max_heap_percolate_down() function takes the following arguments:
node_index
heap_list
list_size
blank: index of the node to be percolated down
node_index
blank: list that stores the heap’s contents
heap_list
blank: an integer representing the heap’s size
list_size
The heap sort algorithm requires operating on a subset of the heap contents, so the list_size argument is required and may not be equal to blank.
len(heap_list)
The heap_sort() function takes a single argument:blank The list is heapified first, then the maximum is removed repeatedly, and the sorted list is built in reverse order.
the list of items to be sorted.
def max_heap_percolate_down(node_index, heap_list, list_size):
child_index = 2 * node_index + 1
value = heap_list[node_index]
while child_index < list_size:
# Find the max among the node and all the node's children
max_value = value
max_index = -1
i = 0
while i < 2 and i + child_index < list_size:
if heap_list[i + child_index] > max_value:
max_value = heap_list[i + child_index]
max_index = i + child_index
i = i + 1
if max_value == value:
return
# Swap heap_list[node_index] and heap_list[max_index]
temp = heap_list[node_index]
heap_list[node_index] = heap_list[max_index]
heap_list[max_index] = temp
node_index = max_index
child_index = 2 * node_index + 1
Sorts the list of numbers using the heap sort algorithm
def heap_sort(numbers):
# Heapify numbers list
i = len(numbers) // 2 - 1
while i >= 0:
max_heap_percolate_down(i, numbers, len(numbers))
i = i - 1
i = len(numbers) - 1
while i > 0:
# Swap numbers[0] and numbers[i]
temp = numbers[0]
numbers[0] = numbers[i]
numbers[i] = temp
max_heap_percolate_down(0, numbers, i)
i = i - 1
Heap sort algorithm.
A blank is a queue where each item has a priority, and items with higher priority are closer to the front of the queue than items with lower priority.
priority queue
The priority queue blank operation inserts an item such that the item is closer to the front than all items of lower priority, and closer to the end than all items of equal or higher priority.
enqueue
The priority queue blank operation removes and returns the item at the front of the queue, which has the highest priority.
dequeue
A blank operation returns the highest priority item, without removing the item from the front of the queue.
peek
Inserts x after all equal or higher priority items
Enqueue(PQueue, x)
Returns and removes the item at the front of PQueue
Dequeue(PQueue)
Returns but does not remove the item at the front of PQueue
Peek(PQueue)
Returns true if PQueue has no items
IsEmpty(PQueue)
Returns the number of items in PQueue
GetLength(PQueue)
A priority queue can be implemented such that each item’s priority can be determined from the blank. Ex: A customer object may contain information about a customer, including the customer’s name and a service priority number. In this case, the priority resides within the object.
item itself
A priority queue may also be implemented such that all priorities are specified during a call to blank:
EnqueueWithPriority
A priority queue is commonly implemented using a heap. A heap will keep the highest priority item in the root node and allow access in blank time. Adding and removing items from the queue will operate in worst-case blank
O(1)
O(logN) time
Enqueue Worst-case runtime complexity
O(logN)
Dequeue Worst-case runtime complexity
O(logN)
Peek Worst-case runtime complexity
O(1)
isEmpty Worst-case runtime complexity
O(1)
GetLength Worst-case runtime complexity
O(1)
A blank uses a main key that maintains a binary search tree ordering property, and a secondary key generated randomly (often called “priority”) during insertions that maintains a heap property. The combination usually keeps the tree balanced.
treap
A treap blank is the same as a BST search using the main key, since the treap is a BST.
search
A treap blank initially inserts a node as in a BST using the main key, then assigns a random priority to the node, and percolates the node up until the heap property is not violated. In a heap, a node is moved up via a swap with the node’s parent. In a treap, a node is moved up via a rotation at the parent. Unlike a swap, a rotation maintains the BST property.
insert
A treap blank can be done by setting the node’s priority such that the node should be a leaf (-∞ for a max-heap), percolating the node down using rotations until the node is a leaf, and then removing the node.
delete
A treap delete could be done by first doing a BST delete (copying the successor to the node-to-delete, then deleting the original successor), followed by percolating the node down until the heap property is not violated. However, a simpler approach just sets the node-to-delete’s blank to -∞ (for a max-heap), percolates the node down until a leaf, and removes the node
priority
