Package org.drip.graph.softheap

Class ApproximatePriorityQueue<KEY extends java.lang.Comparable<KEY>,ITEM>

java.lang.Object

org.drip.graph.heap.PriorityQueue<KEY,ITEM>

org.drip.graph.softheap.ApproximatePriorityQueue<KEY,ITEM>

public abstract class ApproximatePriorityQueue<KEY extends java.lang.Comparable<KEY>,ITEM>
extends PriorityQueue<KEY,ITEM>

ApproximatePriorityQueue exposes the Functions Approximate Priority Queue with Optimal Error Rate. The References are:

• Blum, M., R. W. Floyd, V. Pratt, R. L. Rivest, and R. E. Tarjan (1973): Time Bounds for Selection Journal of Computer and System Sciences 7 (4) 448-461
• Chazelle, B. (2000): The Soft Heap: An Approximate Priority Queue with Optimal Error Rate Journal of the Association for Computing Machinery 47 (6) 1012-1027
• Chazelle, B. (2000): A Minimum Spanning Tree Algorithm with Inverse-Ackerman Type Complexity Journal of the Association for Computing Machinery 47 (6) 1028-1047
• Fredman, M. L., and R. E. Tarjan (1987): Fibonacci Heaps and their Uses in Improved Network Optimization Algorithms Journal of the Association for Computing Machinery 34 (3) 596-615
• Vuillemin, J. (2000): A Data Structure for Manipulating Priority Queues Communications of the ACM 21 (4) 309-315

• Module = Computational Core Module
• Library = Graph Algorithm Library
• Project = Graph Optimization and Tree Construction Algorithms
• Package = Soft Heap - Approximate Priority Queue

Author:

Lakshmi Krishnamurthy

Method Summary

Modifier and Type	Method	Description
abstract double	impliedErrorRate()	Compute the Implied Error Rate
int	r()	Retrieve the R Parameter

Methods inherited from class org.drip.graph.heap.PriorityQueue

delete, extractExtremum, extremum, insert, isEmpty, meld, minHeap, sortedEntryList, sortedItemList, sortedKeyList

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Details

r

public int r()

Retrieve the R Parameter

Returns:

The R Parameter

impliedErrorRate

public abstract double impliedErrorRate()

Compute the Implied Error Rate

Returns:

The Implied Error Rate