Ch 5: Heaps

Question 1

what is a max-heap?

Answer 1

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

Question 2

what is the root node?

Answer 2

a node with the maximum key in the entire tree, and therefore has no parents

Question 3

what is insert?

Answer 3

an operation that inserts the node into the tree’s last level then swaps node with the parent until no max-heap property violation occurs

Question 4

how is a level added and when is a new level added during insert?

Answer 4

a level is filled left to right before adding another level so that the tree’s height is always the minimum possible

Question 5

what is percolating?

Answer 5

an upward movement of a node in a max-heap

Question 6

what is remove?

Answer 6

an operation that removes the root node 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

Question 7

what is the height of a max-heap?

Answer 7

logN

Question 8

what is a min-heap?

Answer 8

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

Question 9

how are heaps typically implemented?

Answer 9

arrays

Question 10

what is used to refer to the nodes?

Answer 10

indices, not pointers since it is an array and not linked list

Question 11

what is the formula to find the parent index from the child index?

Answer 11

lower of (i-1)/2

Question 12

what is the formula to find the child index/indices from the parent index

Answer 12

(2i)+1 / (21i)+2

Question 13

what is heap sort?

Answer 13

• 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
• sorts from least to greatest

Question 14

what is heapify?

Answer 14

an operation that is used to turn an array into a heap

Question 15

what is the formula to find the largest internal node index?

Answer 15

lower of N/2 -1

Question 16

explain how heapsort works

Answer 16

1. heapify array into a max-heap and initializing an index value to the size of the array minus 1
2. swap last item w root and lower size by 1 (removes last item)
3. percolate top node down to satisfy heap ordering property
4. repeat until end index is 0

Question 17

explain the heapsort algorithm

Answer 17

• uses 2 loops to sort an array
• first loop heapifies the array using MaxHeapPercolateDown
• second loop removes the maximum value, stores that value at the end index, and decrements the end index, until the end index is 0

Question 18

what is a priority queue?

Answer 18

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

Question 19

what is enqueue for a priority queue?

Answer 19

an operation that 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

Question 20

what is dequeue for a priority queue?

Answer 20

an operation that removes and returns the item at the front of the queue, which has the highest priority

Question 21

is the priority the same for every priority queue?

Answer 21

no, it can be changed for each queue, sometimes it compares the data, sometimes it compares the priority value, sometimes order is least-greatest or greatest-least

Question 22

what is peek for a priority queue?

Answer 22

an operation that returns the highest priority item, without removing the item from the front of the queue

Question 23

what is EnqueueWithPriority for a priority queue?

Answer 23

an enqueue operation that includes an argument for the enqueued item’s priority

Question 24

what is the common way to implement priority queues?

Answer 24

heaps

Question 25

what is sorting?

Answer 25

the process of converting a list of elements into ascending or descending order

Question 26

what is shell sort?

Answer 26

a sorting algorithm that treats the input as a collection of interleaved lists, and sorts each list individually with a variant of the insertion sort algorithm

Question 27

what is a gap value?

Answer 27

a positive integer representing the distance between elements in an interleaved list

Question 28

how are gap values used in shell sort?

Answer 28

shell sort uses gap values to determine the number of interleaved lists

Question 29

how are interleaved lists created?

Answer 29

1. starting at the first index, that node is part of list 1
2. the next node for that list is the current node’s index + gap value
3. continue until end of list is reached
4. then go back to first index and move over by 1, repeat list creation until all nodes are separated

Question 30

does shell sort work if the interleaved lists do not have the same amount of elements?

Answer 30

yes, some lists may have less elements than the others but shell sort still works

Question 31

what is quicksort?

Answer 31

a sorting algorithm that repeatedly partitions the input into low and high parts(each part is unsorted) and then recursively sorts each of those parts

Question 32

what is a pivot?

Answer 32

any value within the array being sorted, commonly the value of the middle array element

Question 33

how is a pivot used in quicksort?

Answer 33

to partition the input, quicksort chooses a pivot to divide the data into low and high parts

Question 34

what is merge sort?

Answer 34

a sorting algorithm that divides a list into two halves recursively sorts each half, then merges the sorted halves to produce a sorted list, the recursive partitioning continues until a list of 1 element is reached, as a list of 1 element is already sorted

Question 35

what is radix sort?

Answer 35

a sorting algorithm specifically for an array of integers

Question 36

what is a bucket

Answer 36

a collection of integer values that all share a particular digit value

Question 37

how do buckets relate to radix sort?

Answer 37

the algorithm makes use of buckets and is a type of bucket sort

Question 38

what is a fast sorting algorithm?

Answer 38

a sorting algorithm that has an average runtime complexity of O(NlogN) or better

Question 39

what is an element comparison sorting algorithm?

Answer 39

a sorting algorithm that operates on an array of elements that can be compared to each other

Question 40

explain insert algorithm for heaps

Answer 40

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 called percolating.

Question 41

explain remove algorithm for heaps

Answer 41

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.