Implementation of Priority Queue
A priority queue is an abstract data type similar to a regular queue or stack data structure in which each element additionally has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority.
A common misconception is that a Heap is the same as a Priority Queue, which is not true. A priority queue is an abstract data type, while a Heap is a data structure. Therefore, a Heap is not a Priority Queue, but a way to implement a Priority Queue.
There are multiple ways to implement a Priority Queue, such as array and linked list. However, these implementations only guarantee O(1) time complexity for either insertion or deletion, while the other operation will have a time complexity of O(N)O(N). On the other hand, implementing the priority queue with Heap will allow both insertion and deletion to have a time complexity of O(logN).
Priority Queue/Heap 维护了一个每次poll都是最小元素。是用complete binary tree实现。
所谓的"完全二叉树", 要满足:
除了最后一层, 所有层都排满(没有非空节点)
最后一层的所有非空节点都排在左边
一张图可以直观说明, 完全二叉树其实就是长得像这样:
A heap is a binary tree that meets the following criteria:
Is a complete binary tree;
The value of each node must be no greater than (or no less than) the value of its child nodes.
There are two kinds of heaps: Max Heap and Min Heap.
Max Heap: Each node in the Heap has a value no less than its child nodes. Therefore, the top element (root node) has the largest value in the Heap. (value of node >= values of children)
Min Heap: Each node in the Heap has a value no larger than its child nodes. Therefore, the top element (root node) has the smallest value in the Heap. (value of node <= values of children)
min heap 操作：
peek(): 返回数组的第一个元素的值，root节点总是最大/小值。time complexity: O(1)
insert(): 插入一个新的元素，总是放在数组元素的最后一个位置，然后heapifyUp，调整heap满足min heap。time complexity: O(logN)
poll(): 拿出数组的第一个元素，heap中剩下的元素要进行调整，保证heap是min heap的结构，这个过程是heapifyDown。time complexity: O(logN)
heapifyUp: 数组新增的最后一个元素与其parent进行比较， 如果新增元素的值小于其parent的值，则进行交换，递归此过程。时间复杂度是O(lgn)。
heapifyDown: 把最后一个元素放到root的位置，从root位置开始，比较root位置代表的parent与其左右children的大小，parent总是与children中元素较小的进行交换。 重复这个过程，直到大的元素不再有children。时间复杂度是O(lgn)。
build树的时候，因为有n个node，每加入一个都要heapify，所以时间复杂度是O(nlgn)
public class MinHeap {
// Create a complete binary tree using an array
// Then use the binary tree to construct a Heap
int[] minHeap;
// the number of elements is needed when instantiating an array
// heapSize records the size of the array
int heapSize;
// realSize records the number of elements in the Heap
int realSize = 0;
public MinHeap(int heapSize) {
this.heapSize = heapSize;
minHeap = new int[heapSize + 1];
// To better track the indices of the binary tree, we will not use the 0-th element in the array
// You can fill it with any value
minHeap[0] = 0;
}
// Function to add an element
public void add(int element) {
realSize++;
// If the number of elements in the Heap exceeds the preset heapSize
// print "Added too many elements" and return
if (realSize > heapSize) {
System.out.println("Added too many elements!");
realSize--;
return;
}
// Add the element into the array
minHeap[realSize] = element;
// Index of the newly added element
int index = realSize;
// Parent node of the newly added element
// Note if we use an array to represent the complete binary tree and store the root node at index 1
// - index of the parent node of any node is [index of the node / 2]
// - index of the left child node is [index of the node * 2]
// - index of the right child node is [index of the node * 2 + 1]
int parent = index / 2;
// If the newly added element is smaller than its parent node,
// its value will be exchanged with that of the parent node
while ( minHeap[index] < minHeap[parent] && index > 1 ) {
int temp = minHeap[index];
minHeap[index] = minHeap[parent];
minHeap[parent] = temp;
index = parent;
parent = index / 2;
}
}
// Get the top element of the Heap
public int peek() {
return minHeap[1];
}
// Delete the top element of the Heap
public int pop() {
// If the number of elements in the current Heap is 0,
// print "Don't have any elements" and return a default value
if (realSize < 1) {
System.out.println("Don't have any element!");
return Integer.MAX_VALUE;
} else {
// When there are still elements in the Heap
// realSize >= 1
int removeElement = minHeap[1];
// Put the last element in the Heap to the top of Heap
minHeap[1] = minHeap[realSize];
realSize--;
int index = 1;
// When the deleted element is not a leaf node
while (index <= realSize / 2) {
// the left child of the deleted element
int left = index * 2;
// the right child of the deleted element
int right = (index * 2) + 1;
// If the deleted element is larger than the left or right child,
// its value needs to be exchanged with the smaller value of the left and right child
if (minHeap[index] > minHeap[left] || minHeap[index] > minHeap[right]) {
if (minHeap[left] < minHeap[right]) {
int temp = minHeap[left];
minHeap[left] = minHeap[index];
minHeap[index] = temp;
index = left;
} else {
// maxHeap[left] >= maxHeap[right]
int temp = minHeap[right];
minHeap[right] = minHeap[index];
minHeap[index] = temp;
index = right;
}
} else {
break;
}
}
return removeElement;
}
}
// return the number of elements in the Heap
public int size() {
return realSize;
}
public String toString() {
if (realSize == 0) {
return "No element!";
} else {
StringBuilder sb = new StringBuilder();
sb.append('[');
for (int i = 1; i <= realSize; i++) {
sb.append(minHeap[i]);
sb.append(',');
}
sb.deleteCharAt(sb.length() - 1);
sb.append(']');
return sb.toString();
}
}
public static void main(String[] args) {
// Test case
MinHeap minHeap = new MinHeap(3);
minHeap.add(3);
minHeap.add(1);
minHeap.add(2);
// [1,3,2]
System.out.println(minHeap.toString());
// 1
System.out.println(minHeap.peek());
// 1
System.out.println(minHeap.pop());
// [2, 3]
System.out.println(minHeap.toString());
minHeap.add(4);
// Add too many elements
minHeap.add(5);
// [2,3,4]
System.out.println(minHeap.toString());
}
}
Last updated