Priority Queues Quiz: Heaps and Adaptable Priority Queues in Computer Science

Study Notes

Priority Queue ADT

A priority queue is a ADT for storing a collection of prioritized elements.
It supports arbitrary inserts and removal of elements in order of priority.
Stores elements according to their priority and exposes no notion of position to the user.
Key: Object assigned to an element which can be used to identify or weigh that element.
Keys are not necessarily unique and can be of any type.

Entries and Total Orders

Entries: An entry in a priority queue is a key-value pair.
Methods: key(): returns the key for this entry, value(): returns the value associated with this entry.
Total Order Relations: Keys in a priority queue can be arbitrary objects on which an order is defined.
Reflexive property: x ≤ x, Antisymmetric property: x ≤ y ∧ y ≤ x ⇒ x = y, Transitive property: x ≤ y ∧ y ≤ z ⇒ x ≤ z.

Priority Queue Methods

insert(k, x): inserts an entry with key k and value x.
removeMin(): removes and returns the entry with smallest key.
min(): returns, but does not remove, an entry with smallest key.
size(): returns the number of elements in the priority queue.
isEmpty(): returns true if the priority queue is empty, false otherwise.

Comparator ADT

A comparator encapsulates the action of comparing two objects according to a given total order relation.
A generic priority queue uses an auxiliary comparator.
The comparator is external to the keys being compared.
The primary method of the Comparator ADT: compare(x, y): returns an integer i such that i < 0 if a < b, i = 0 if a = b, and i > 0 if a > b.

Heap ADT

Height of a Heap: The height of a heap is the number of nodes in the longest path from the root to a leaf.
For a heap with n nodes, the height is at most logn.

Heaps and Priority Queues

A heap can be used to implement a priority queue.
We store a (key, element) item at each node.
We keep track of the position of the last node.

Insertion into a Heap

Insertion into a heap is done by inserting a key k into the heap.
It corresponds to the insertion of a key k to the heap.

Priority Queue Sorting

A priority queue can be used to sort a set of comparable elements.
Insert the elements one by one with a series of insert operations.
Remove the elements in sorted order with a series of removeMin operations.
The running time of this sorting method depends on the priority queue implementation.

Adaptable Priority Queue ADT

An adaptable priority queue is a priority queue that allows the priorities of its entries to be modified.
It supports operations to increase or decrease the priority of an entry.
It can be used in applications where priorities need to be updated dynamically.

ArrayList-Based Heap Implementation

An array-based implementation of a heap.
The heap is stored in an array, where the parent node is at index i, and the left and right child nodes are at indices 2i+1 and 2i+2 respectively.

Merging Two Heaps

Merging two heaps is done by combining the two heaps into a single heap.
It can be done by inserting the elements of the second heap into the first heap.

Downheap Analysis

Downheap analysis is used to analyze the time complexity of heap operations.
It is used to show that the time complexity of inserting an element into a heap is O(logn).

Location-Aware Entries

Location-aware entries are entries that keep track of their location in the heap.
They can be used to implement an adaptable priority queue.

Location-Aware list Implementation

A list-based implementation of a location-aware heap.
The heap is stored in a list, where each node keeps track of its location in the list.

Description

Test your understanding of priority queue ADT, heap ADT, and adaptable priority queue ADT, including their properties, methods, and applications in computer science. This quiz covers topics from Lecture 7 of Computer Science 3A (CSC3A10) at the University of Johannesburg. Evaluate your knowledge of comparator ADT and priority queue sorting.