Heap / PriorityQueue

Last Updated: 2024-01-17

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.

https://pkg.go.dev/container/heap