Priority queue with heaps in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a priority queue?

A priority queue is a special type of queue where each element has a priority. Elements with higher priority are served before elements with lower priority, unlike a normal queue which follows first-in-first-out order.

beginner

How does a heap help implement a priority queue?

A heap is a special tree-based structure that keeps the highest (or lowest) priority element at the root. This makes it easy and fast to get the element with the highest priority, which is needed for a priority queue.

beginner

What is the difference between a max-heap and a min-heap?

In a max-heap, the parent node is always greater than or equal to its children, so the largest element is at the root. In a min-heap, the parent node is always less than or equal to its children, so the smallest element is at the root.

intermediate

What is the time complexity to insert an element into a heap-based priority queue?

Inserting an element into a heap-based priority queue takes O(log n) time, where n is the number of elements. This is because the element may need to move up the tree to maintain the heap property.

intermediate

How do you remove the highest priority element from a heap?

To remove the highest priority element (the root), you replace it with the last element in the heap, then adjust the heap by moving this element down (heapify) to restore the heap property. This takes O(log n) time.

What does a priority queue always return when you remove an element?

A A random element

B The element that was added first

C The element with the lowest priority

D The element with the highest priority

A priority queue always removes and returns the element with the highest priority.

Which data structure is commonly used to efficiently implement a priority queue?

A Heap

B Linked list

C Array

D Stack

Heaps allow quick access to the highest priority element, making them ideal for priority queues.

In a max-heap, where is the largest element located?

A At the rightmost leaf

B At the leftmost leaf

C At the root

D At the middle level

The largest element in a max-heap is always at the root node.

What is the worst-case time complexity to remove the highest priority element from a heap?

A O(log n)

B O(n)

C O(1)

D O(n log n)

Removing the root and restoring the heap property takes O(log n) time.

Which operation is NOT typical for a priority queue?

A Remove element with highest priority

B Remove element from the middle without priority consideration

C Peek at element with highest priority

D Insert element with priority

Priority queues do not support removing arbitrary elements without considering priority.

Explain how a heap maintains the priority queue property during insertion and removal.

Think about how the tree structure changes to keep the highest priority element at the root.

Describe the difference between a max-heap and a min-heap and how each relates to priority queues.

Consider which element you want to access first in your priority queue.