Priority Queue

Front 1

what data type do you use when you need to extract things based on a score/weight for each item?

Back 1

a priority queue

Front 2

what is the api for a max priority queue?

Back 2

create(), create(capacity), insert(key), max(), delete_max(), is_empty(), size()

Front 3

what are some applications of a priority queue?

Back 3

event-driven simulation (do the highest priorty event first), huffman codes, dijkstra's algorithm, prim's algorithm, A*, maintain largest M items,

Front 4

how do you find the top M items in a list of N items where N is huge?

Back 4

use a minimum priority queue and while iterating through each of the N items add it to the queue, but whenever the queue exceeds size M pop the smallest off the queue

Front 5

what is a binary max heap?

Back 5

a complete binary tree where every element is greater than or equal to its children

Front 6

what is the height of a complete binary tree? How do you prove it?

Back 6

1+floor(lg(n)), height only increases when n is a power of 2

Front 7

how does the array representation of a binary max heap based priority queue work?

Back 7

the largest element is in a[1], parent of node at k is at floor(k/2)

a variable is used to keep track of the index for the number of elements in the array

children of node at k are at 2k and 2k+1

Front 8

how is the position where a node can be inserted into a heap kept track of?

Back 8

in the array implementation the location of the node the size of the binary heap so far +1. in a pointer based implementation a queue can be maintained of nodes who can have children added, whenever a node is added it gets added to the queue

Front 9

how does insert(value) work?

Back 9

a node is created in the last position of the heap containing the new value and then it is floated until it is smaller than its parent

Front 10

how does float(node_id) work?

Back 10

while the value at node_id is greater than its parent swap the values of the parent and node_id

Front 11

how does delete_max() work?

Back 11

replace the root of the heap with the last element in the heap and then let the new root value sink down the heap

Front 12

how does sink(node_id) work?

Back 12

while node_id's value is smaller than one of its children, swap it with the larger of the children. do this again with the swapped child

Front 13

what is the advantage of heapsort over other asymptotically optimal sorts?

Back 13

it can be done in-place i.e. using a small amount of extra memory O(log n)

Front 14

what is the idea for an in-place heapsort of ascending items given an arbitrary array?

Back 14

create a max-heap using a bottom-up construction

remove the elements from the heap in-place by swapping them with the last position in the heap (moving this down w/ each removal)

Front 15

how do you do turn an array into a heap in-place?

Back 15

sink the interior nodes starting from the parent of the last position (N/2) go through the interior nodes bottom-up in level order by decrementing the the current node until the root is reached

Front 16

how do you remove the items of a heap in-place so that the items in the array are in order?

Back 16

exchange the root with the element in the last position decrement where the last position is then sink the root, repeat until the last position is the root

Front 17

what is the complexity of heapsort?

Back 17

nlogn to make the heap, nlogn to remove all the elements so O(nlogn)
with constant space