Heap / PriorityQueue
Python
from heapq import heappush, heappop
heap = []
heappush(heap, 1)
heappop(heap)
Java
Java provides PriorityQueue
and PriorityBlockingQueue
.
Simple case: integers
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(1);
pq.offer(5);
pq.offer(2);
pq.offer(10);
pq.offer(3);
while (!pq.isEmpty()) {
System.out.print(pq.poll() + " ");
}
Dealing with objects(Java 8+):
import java.util.PriorityQueue;
PriorityQueue<Pair> pq = new PriorityQueue<>((Pair x, Pair y) -> x.priority - y.priority);
pq.offer(new Pair(1, 1));
pq.offer(new Pair(2, 10));
pq.offer(new Pair(3, 5));
pq.offer(new Pair(4, 9));
pq.offer(new Pair(5, 2));
while (!pq.isEmpty()) {
System.out.print(pq.poll().value + " ");
}
The definition of Pair:
class Pair {
int value;
int priority;
Pair(int v, int p) {
value = v;
priority = p;
}
}
Go
Go has a container/heap
, but it's just the interface, you need to add your own impl.