Index Min P Q Algorithm
The Index Min P Q Algorithm is an efficient data structure that enables the retrieval of the minimum element from a collection of elements while supporting operations like insertion, deletion, and modification in logarithmic time. It is an advanced version of the priority queue, with the additional functionality of indexing, which enables quick access to the elements based on their indices. This algorithm is widely used in various applications such as network simulations, graph algorithms (like Dijkstra's shortest path), and event-driven simulations that involve a large number of elements with dynamic priorities.
The core of the Index Min P Q Algorithm is a binary heap, which is a complete binary tree with the property that each node's value is less than or equal to its children's values. The algorithm maintains two arrays, one for the keys (elements) and the other for the indices. The keys array stores the elements, while the indices array stores their corresponding indices in the keys array. The algorithm supports the following primary operations: insert (inserting a new element with a specific index), delete (removing the minimum element), decreaseKey (decreasing the key value of a specific element), and minIndex (retrieving the index of the minimum element). These operations can be performed in O(log N) time complexity, where N is the number of elements in the data structure, making the Index Min P Q Algorithm an efficient solution for various computational problems.
package org.gs.queue
import scala.reflect.ClassTag
/** Minimum priority queue with index
*
* @constructor creates a new IndexMinPQ with maximum number of elements
* @tparam A keys are generic and ordered
* @param nMax maximum number of elements
* @param ord implicit ordering
* @see [[https://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html]]
* @author Scala translation by Gary Struthers from Java by Robert Sedgewick and Kevin Wayne.
*/
class IndexMinPQ[A: ClassTag](nMax: Int)(implicit ord: Ordering[A]) extends IndexPriorityQueue[A](nMax) {
/** Add key to end of array then swim up to ordered position
*
* @param i index where key will be inserted if not already there
* @param key generic element
*/
def insert(i: Int, key: A): Unit = insert(i, key, greater)
/** returns index associated with min key */
def minIndex(): Int = index
/** returns min key */
def minKey(): A = topKey
/** returns min key and removes it from queue */
def delMin(): Int = delTop(greater)
/** Change key at index to new value, because it can be > or < current, it both swims and sinks
*
* @param i index
* @param key value
*/
def changeKey(i: Int, key: A): Unit = changeKey(i, key, greater)
/** Decrease key at index to new value, because it is < current, it swims
*
* @param i index
* @param key value
*/
def decreaseKey(i: Int, key: A): Unit = decreaseKey(i, key, greater)
/** Increase key at index to new value, because it is > current, it sinks
*
* @param i index
* @param key value
*/
def increaseKey(i: Int, key: A): Unit = increaseKey(i, key, greater)
/** Remove key at index
*
* @param i index
*/
def delete(i: Int): Unit = delete(i, greater)
/** check parent in position has left child at k * 2, right child at k * 2 + 1 */
def isMinHeap(): Boolean = checkHeap(greater)
/** returns keys in order */
def keys(): Seq[A] = getKeys
}
