Heaps and Treaps - Chapter 7

Question 1

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.

Answer 1

max-heap

Question 2

a max-heap’s blank always has the maximum key in the entire tree.

Answer 2

root

Question 3

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.

Answer 3

insert

Question 4

The upward movement of a node in a max-heap is called blank.

Answer 4

percolating

Question 5

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

Answer 5

remove

Question 6

what is the height of a max-heap?

Answer 6

floor(logN)

Question 7

Given a max-heap with N nodes, what is the worst-case complexity of an insert, assuming an insert is dominated by the swaps?

Answer 7

O(logN)

Question 8

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?

Answer 8

3

Question 9

Given a max-heap with N nodes, what is the complexity for removing the root?

Answer 9

O(logN)

Question 10

A blank is similar to a max-heap, but a node’s key is less than or equal to its children’s keys.

Answer 10

min-heap

Question 11

A customer with a higher priority has a blank numerical value in the min-heap.

Answer 11

lower

Question 12

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.

Answer 12

arrays

Question 13

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.

Answer 13

index

Question 14

Node index 0 Parent index ? Child indices ?

Answer 14

None
1,2

Question 15

Node index 1 Parent index ? Child indices ??

Answer 15

0
3,4

Question 16

Node index 2 Parent index ? Child indices ?

Answer 16

0
5,6

Question 17

Node index 3 Parent index ? Child indices ?

Answer 17

1
7,8

Question 18

Node index 4 Parent index? Child indices?

Answer 18

1
9, 10

Question 19

Node index 5 Parent index ? Child indices??

Answer 19

2
11, 12

Question 20

Node index i Parent index ? Child indices??

Answer 20

floor((i-1)/2)
2 * i +1, 2* i + 2

Question 21

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
}
}
}

Answer 21

Max-heap percolate up algorithm.

Question 22

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
  }    } }

Answer 22

Max-heap percolate down algorithm.

Question 23

blank = (node_index - 1) // 2

Answer 23

parent_index

Question 24

blank = 2 * node_index + 1

Answer 24

left_child_index

Question 25

blank = 2 * node_index + 2

Answer 25

right_child_index

Question 26

The MaxHeap methods blank and blank make use of two methods, percolate_up() and percolate_down().

Answer 26

insert() and remove()

Question 27

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.

Answer 27

percolate_up()

Question 28

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.

Answer 28

percolate_down()

Question 29

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.

Answer 29

insert() method

Question 30

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.

Answer 30

remove() method

Question 31

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.

Answer 31

Heapsort

Question 32

An array of unsorted values must first be converted into a heap. The blank operation is used to turn an array into a heap.

Answer 32

heapify

Question 33

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.

Answer 33

percolating down

Question 34

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

Answer 34

floor(N/2) - 1

Question 35

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.

Answer 35

0

Question 36

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.

Answer 36

2 loops

Question 37

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.

Answer 37

percolate down

Question 38

The max_heap_percolate_down() function takes the following arguments:

Answer 38

node_index
heap_list
list_size

Question 39

blank: index of the node to be percolated down

Answer 39

node_index

Question 40

blank: list that stores the heap’s contents

Answer 40

heap_list

Question 41

blank: an integer representing the heap’s size

Answer 41

list_size

Question 42

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.

Answer 42

len(heap_list)

Question 43

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.

Answer 43

the list of items to be sorted.

Question 44

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

Answer 44

Heap sort algorithm.

Question 45

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.

Answer 45

priority queue

Question 46

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.

Answer 46

enqueue

Question 47

The priority queue blank operation removes and returns the item at the front of the queue, which has the highest priority.

Answer 47

dequeue

Question 48

A blank operation returns the highest priority item, without removing the item from the front of the queue.

Answer 48

peek

Question 49

Inserts x after all equal or higher priority items

Answer 49

Enqueue(PQueue, x)

Question 50

Returns and removes the item at the front of PQueue

Answer 50

Dequeue(PQueue)

Question 51

Returns but does not remove the item at the front of PQueue

Answer 51

Peek(PQueue)

Question 52

Returns true if PQueue has no items

Answer 52

IsEmpty(PQueue)

Question 53

Returns the number of items in PQueue

Answer 53

GetLength(PQueue)

Question 54

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.

Answer 54

item itself

Question 55

A priority queue may also be implemented such that all priorities are specified during a call to blank:

Answer 55

EnqueueWithPriority

Question 56

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

Answer 56

O(1)
O(logN) time

Question 57

Enqueue Worst-case runtime complexity

Answer 57

O(logN)

Question 58

Dequeue Worst-case runtime complexity

Answer 58

O(logN)

Question 59

Peek Worst-case runtime complexity

Answer 59

O(1)

Question 60

isEmpty Worst-case runtime complexity

Answer 60

O(1)

Question 61

GetLength Worst-case runtime complexity

Answer 61

O(1)

Question 62

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.

Answer 62

treap

Question 63

A treap blank is the same as a BST search using the main key, since the treap is a BST.

Answer 63

search

Question 64

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.

Answer 64

insert

Question 65

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.

Answer 65

delete

Question 66

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

Answer 66

priority