WEEK 8 2200

What is a priority queue?

A data structure that stores a collection of items, each represented as a pair (key, value).

What does the add(k, x) method do in a priority queue?

Inserts an item with key k and value x.

What is the purpose of the remove_min() method?

Removes and returns the item with the smallest key.

What does the min() method do?

Returns but does not remove the item with the smallest key.

What is the time complexity of add in an unsorted list implementation of a priority queue?

O(1)

What is the time complexity of remove_min in an unsorted list implementation?

O(n)

What is the time complexity of add in a sorted list implementation of a priority queue?

O(n)

What is the time complexity of remove_min in a sorted list implementation?

O(1)

What is a total order relation?

A mathematical concept that defines an order among arbitrary objects, satisfying reflective, antisymmetric, and transitive properties.

What is the reflective property of total order relations?

For any element x, x <= x.

What is the antisymmetric property of total order relations?

If x <= y and y <= x, then x = y.

What is the transitive property of total order relations?

If x <= y and y <= z, then x <= z.

How can a priority queue be used for sorting?

By inserting elements with add operations and then removing them in sorted order with remove_min operations.

What is the running time of selection sort using a priority queue?

O(n^2)

What is the running time of insertion sort using a priority queue?

O(n^2)

What is the difference between selection sort and insertion sort in terms of priority queue implementation?

Selection sort uses an unsorted sequence, while insertion sort uses a sorted sequence.

What are some applications of priority queues?

Standby flyers, auctions, stock market.

What does the is_empty() method do in a priority queue?

Checks if the priority queue is empty.

What does the len(P) method return?

The number of items in the priority queue P.

What is a heap?

A binary tree storing keys at its nodes that satisfies the heap order and complete binary tree properties.

What is the heap order property?

For every internal node v other than the root, key(v) >= key(parent(v)).

What is the height of a heap storing n keys?

O(log n).

How is the height of a heap proven?

By applying the complete binary tree property and showing that n >= 2^h.

How can heaps be used in data structures?

Heaps can be used to implement priority queues.

What are the steps for inserting a key into a heap?

Find the insertion node, store the key, and restore the heap order property.

What is the purpose of the upheap algorithm?

To restore the heap order property after inserting a new key.

When does upheap terminate?

When the key reaches the root or a node whose parent has a key smaller than or equal to it.

What are the steps for removing the root key from a heap?

Replace the root key with the last node's key, remove the last node, and restore the heap order property.

What is the purpose of the downheap algorithm?

To restore the heap order property after removing the root key.

When does downheap terminate?

When the key reaches a leaf or a node whose children have keys greater than or equal to it.

How can the last node in a heap be updated?

By traversing a path of O(log n) nodes to find the insertion node.

What is heap sort?

An algorithm that sorts a sequence of n elements in O(n log n) time using a heap-based priority queue.

What is the space complexity of a heap-based priority queue?

O(n).

How is a heap represented in an array?

For a node at rank i, the left child is at rank 2i + 1 and the right child at rank 2i + 2.

What happens when merging two heaps?

A new heap is created with a root node storing a key and the two heaps as subtrees, followed by downheap to restore order.

What is bottom-up heap construction?

A method to construct a heap storing n keys in log n phases by merging pairs of heaps.

What is the time complexity of bottom-up heap construction?

O(n).

Why is bottom-up heap construction faster than successive insertions?

It reduces the number of operations needed to build the heap compared to inserting each key one at a time.

What is the time complexity for the add and remove_min methods in a heap?

O(log n).

What is the time complexity for the len, is_empty, and min methods in a heap?

O(1).

What is the significance of the complete binary tree property in heaps?

It ensures that the heap is balanced, allowing efficient operations.

How does the number of nodes in a heap relate to its height?

The number of nodes is at least 2^h, where h is the height of the heap.