7 PRIORITY QUEUES AND HEAPS Flashcards
What is a priority queue?
A class of data structures that retrieves items ordered by given scores for each item.
How do priority queues differ from stacks and queues?
Priority queues use an additional piece of information, the item’s priority, to determine the retrieval order.
What is an example of a real-world application of a priority queue?
Processing urgent requests first, such as choosing which patient to see first in a crowded emergency room.
What are the primary operations supported by a basic priority queue?
- Add an item and its associated priority score. * Look up the item with the highest priority. * Remove the item with the highest priority.
What is a max heap?
A variant of the binary tree that maintains a special ordered relationship where the value at any node is larger than or equal to the values of its child nodes.
What is the max heap property?
The property that states the value at any node in the tree is larger than or equal to the values of its child nodes.
Who originally invented heaps?
Computer scientist J. W. J. Williams.
How are heaps typically implemented for efficiency?
Heaps are often visualized as trees but implemented with arrays.
In an array-based heap implementation, where is the root node stored?
At index 1 of the array.
What is the cost of looking up the maximum value in a max heap?
Constant time.
When adding a new element to a heap, what must be ensured?
The structure retains the heap property.
What does it mean to bubble up an element in a heap?
To swap the new element with its parent node until the heap property is restored.
What happens when the last index of the heap reaches the array size?
The heap size must be increased.
What is an efficient way to add a new element to a heap?
Add it to the first empty space in the bottom level and bubble it up.
What is a disadvantage of using a sorted linked list for a priority queue?
Adding new elements can be expensive as it may require traversing the entire list.
What is an advantage of using an unsorted linked list for a priority queue?
Adding new elements is trivial as they can be tagged onto the back of the list.
When should you prefer a sorted list over an unsorted list for a priority queue?
If lookups are more common.
What is the main challenge when both additions and lookups are common in a priority queue?
Prioritizing one operation over the other will lead to overall inefficiency.
What allows heaps to efficiently support operations required for priority queues?
The max heap’s simple structure.
What happens to the maximum value in a max heap when an element is added?
It remains at the root node.
How is the array for a heap typically preallocated?
It is large enough to accommodate the expected number of items.
In a max heap, what is the relationship between a node and its parent?
A node’s value must be less than or equal to its parent’s value.
What is the purpose of the Floor function in heap operations?
To compute the index of a node’s parent.
What is the purpose of the HeapInsert function?
To add a new element to the heap and maintain the heap property
The function checks if there is room in the array, increases the size if necessary, and then inserts the new value while ensuring the heap structure is preserved.
