Skip to content

Instantly share code, notes, and snippets.

@HaoyangFan

HaoyangFan/PriorityQueue.java

Last active July 8, 2019 00:39
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save HaoyangFan/5d942c00fafa51b244f3ddc5fae2637e to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save HaoyangFan/5d942c00fafa51b244f3ddc5fae2637e to your computer and use it in GitHub Desktop.
Download ZIP
Array-based implementation of binary heap, which can be used as priority queue
Raw
PriorityQueue.java
import java.util.Arrays;
/**
* Implementation of a generic max heap (priority queue) following the idea learned.
*
* @param <K> Type of element
*/
public class PriorityQueue<K extends Comparable<? super K>> {
// array-based implementation
private K[] pq;
// number of elements in the priority queue
private int size;
// capacity of the array
private int capacity;
// default capacity
private static final int DEFAULT_CAPACITY = 8;
/**
* Constructor for an empty priority queue using default capacity
*/
@SuppressWarnings("unchecked")
public PriorityQueue() {
pq = (K[]) new Comparable[DEFAULT_CAPACITY];
size = 0;
capacity = DEFAULT_CAPACITY;
}
/**
* Constructor for an empty priority queue using specified capacity
*/
@SuppressWarnings("unchecked")
public PriorityQueue(int c) {
pq = (K[]) new Comparable[c];
size = 0;
capacity = c;
}
/**
* Constructor for building the priority queue based on input elements.
*
* @param inputs input elements
*/
public PriorityQueue(K[] inputs) {
// immutability is important
pq = Arrays.copyOf(inputs, inputs.length << 1);
size = inputs.length;
capacity = inputs.length << 1;
// heapify
for (int i = (inputs.length - 1) / 2; i >= 0; --i) {
siftDown(i);
}
}
private void swap(int idx1, int idx2) {
K tmp = pq[idx1];
pq[idx1] = pq[idx2];
pq[idx2] = tmp;
}
private void siftUp(int idx) {
int parent;
while (idx != 0) {
parent = (idx - 1) / 2;
// stop sifting up in case the heap property of parent node with current node is preserved
if (pq[parent].compareTo(pq[idx]) >= 0) break;
swap(parent, idx);
idx = parent;
}
}
private void siftDown(int idx) {
int kid;
// as long as its left child exists in current heap
while (idx * 2 + 1 < size) {
kid = idx * 2 + 1; // kid now points to its left child
// in case its right child also exist in current heap and has value larger than its left child
if (idx * 2 + 2 < size && pq[idx * 2 + 2].compareTo(pq[kid]) > 0)
kid = idx * 2 + 2; // update kid
// now kid points to the larger of two children
if (pq[idx].compareTo(pq[kid]) >= 0) break;
swap(idx, kid);
idx = kid;
}
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
public void offer(K v) {
pq[size++] = v;
siftUp(size - 1);
}
public K poll() {
K rst = pq[0];
swap(0, --size);
pq[size] = null; // prevent loitering
siftDown(0);
return rst;
}
public K peek() {
return pq[0];
}
@Override
public String toString() {
return Arrays.toString(pq);
}
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>(10);
System.out.println(pq.isEmpty());
pq.offer(1);
pq.offer(2);
pq.offer(3);
System.out.println(pq.size());
System.out.println(pq.peek());
pq.offer(6);
pq.offer(5);
pq.offer(4);
System.out.println(pq.size());
System.out.println(pq.peek());
System.out.println(pq.isEmpty());
System.out.println(pq);
System.out.println(pq.poll());
System.out.println(pq.poll());
System.out.println(pq.poll());
System.out.println(pq.poll());
System.out.println(pq.poll());
System.out.println(pq.poll());
System.out.println(pq);
System.out.println(pq.isEmpty());
pq = new PriorityQueue<>(new Integer[]{1,9,8,7,2,5,4,3,6,0});
System.out.println(pq);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment