Index Max P Q Algorithm
The Index Max P Q Algorithm is a powerful and efficient data structure-based algorithm, primarily used for solving complex computational problems that involve querying and updating an array in a mutable and dynamic environment. This algorithm is particularly useful in performing real-time operations, where the data set is constantly changing, and the answers to queries need to be quickly and accurately determined. The Index Max P Q Algorithm is built on the concept of Priority Queues (PQ), specifically Binary Indexed Tree (BIT) or Fenwick Tree, which allows for efficient updates and queries of the data set. Essentially, the algorithm maintains a PQ for each element of the input array, enabling fast access to the maximum element, and providing the ability to perform range queries, insertions, and deletions in logarithmic time complexity.
The Index Max P Q Algorithm works by first initializing an empty array of PQs, and then populating it with the input data. Each cell in the array contains a separate PQ, which stores the indices of the input array elements that belong to a specific range. The algorithm then processes queries and updates to the array, utilizing the underlying BIT or Fenwick Tree data structure for efficient computations. When performing a range query, the algorithm searches for the maximum element within the specified range by iterating through the PQs in the array and comparing their top elements. In case of an update operation, such as inserting or deleting an element, the algorithm updates the relevant PQs in the array and maintains the internal data structure for future queries. This dynamic nature of the Index Max P Q Algorithm makes it an ideal choice for solving problems in areas such as computational geometry, data mining, and real-time analytics, where the data set is frequently updated and queried for maximum or minimum values within specific ranges.
package org.gs.queue
import scala.reflect.ClassTag
/** Max priority queue with index
*
* @constructor creates a new IndexMaxPQ 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/IndexMaxPQ.java.html]]
* @author Scala translation by Gary Struthers from Java by Robert Sedgewick and Kevin Wayne.
*/
class IndexMaxPQ[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, less)
/** returns index associated with max key */
def maxIndex(): Int = index
/** returns max key */
def maxKey(): A = topKey
/** returns max key and removes it from queue */
def delMax(): Int = delTop(less)
/** 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, less)
/** 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, less)
/** 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, less)
/** Remove key at index
*
* @param i index
*/
def delete(i: Int): Unit = delete(i, less)
/** check parent in position has left child at k * 2, right child at k * 2 + 1 */
def isMinHeap(): Boolean = checkHeap(less)
/** returns keys in order */
def keys(): Seq[A] = getKeys
}
