Priority Queues, Heaps, and Adaptable Priority Queues in Computer Science

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.