Binary heap
First, take a look at baidu Baike’s definition of a complete binary tree.
Complete binary tree: Suppose that the depth of the binary tree is H, except for the h layer, the number of nodes of all other layers (1 ~ H-1) reaches the maximum number, and all nodes of the h layer are continuously concentrated on the left, which is a complete binary tree.
From the diagram, a complete binary tree might look like this:
Notice that a complete binary tree is not necessarily a full binary tree, but a full binary tree must be a complete binary tree.
Binary heap: The essence of a binary heap is the sequential storage of a complete binary tree. If List[0, 1… n-1] represents the sequential storage mode of a complete binary tree, then the following relationship exists between the List subscripts of the parent node and the List subscripts of the child node:
For an arbitrary tree node whose List subscript is I, its: (1) Parent: parent(I) = I == 0? Null: (i-1) / 2 (2) leftchild: leftchild(I) = 2 * I + 1 rightchild: rightchild(I) = 2 * I + 2Copy the codeLarge root heap: A binary heap is called a large root heap if the value of any node I of the binary heap is greater than or equal to the value of its left and right children (if any).
Give a list [0,..., n - 1), length is 2 * n + 1 I < len && list [I] > = list (2 * I + 1] && 2 * I + 2 < len && list [I] > = list (2 * I + 2]Copy the codeSmall root heap: A binary heap is called a small root heap if the value of any node I of the binary heap is less than or equal to the value of its left and right children (if any).
Give a list [0,..., n - 1), length is 2 * n + 1 < I len && list [I] < = list (2 * I + 1] && 2 * I + 2 < len && list [I] < = list (2 * I + 2]Copy the codecode
private int getLeftChildIndex(int root) {
return root * 2 + 1;
}
private int getRightChildIndex(int root) {
return root * 2 + 2;
}
private int getParentIndex(int root) {
if (root == 0) {
throw new UnsupportedOperationException("0 doest't have a parent node");
}
return (root - 1) / 2;
}
Copy the codeWe use the large root heap as an example to describe the operations of heap building, heap sorting, and priority queuing.
Big root pile
Given a List of numbers [0, 1…, n-1], how do you create a large root push? To construct a binary heap, that is, to adjust an unordered complete binary tree to a binary heap, is essentially to legalize all non-leaf nodes in turn (float up or sink down) so that the value of List[I] decreases step by step in the maximum heap. By legalizing the operation, the previously unordered complete binary tree can satisfy the nature of a large root heap. So, first, we’ll introduce this float up operation, in the big root heap implementation, called maxHeapify.
maxHeapify
To give the following example, suppose we now want to adjust the 1 node by maxHeapify. Since the large root heap requires any node I to be greater than or equal to its left and right children, it is obvious that we want to replace 1 with the maximum of its left and right children. After adjustment, the subscript node satisfies the nature of a large root heap relative to its child node. However, after swapping with the child node, the swapped child node may not satisfy the large root heap nature, so further maxHeapify swapped child node.
Time complexity
According to the description extracted from the introduction of the algorithm, for a subtree with root node I and size N, the maxHeapify time complexity is O(LGN), that is, for a node with tree height H, the maxHeapify time complexity is O(h).
code
/** * maxHeapify */ from a node with subscript root
private void maxHeapify(int root, int size) {
int left = getLeftChildIndex(root);
int right = getRightChildIndex(root);
int max = root;
if (left < size && list.get(left) > list.get(root)) {
max = left;
}
if (right < size && list.get(right) > list.get(max)) {
max = right;
}
if (root != max) {
swap(root, max);
maxHeapify(max, size);
}
}
Copy the codebuildMaxHeap
Maximum heap construction, according to the nature of a complete binary tree, the number of leaves is 1 more than the number of internal nodes, so n/ 2-1-0 maxHeapify(maxHeapify from the last non-leaf node forward).
The time complexity is taken from the description in the introduction to algorithms. BuildMaxHeap’s time complexity is O(n), which means that an unordered array or list can be constructed into a large root heap in linear time.
code
/** * build a large root heap, linear time complexity O(n) */
public void buildMaxHeap(a) {
int size = list.size();
for (int i = size / 2 - 1; i >= 0; i--) { maxHeapify(i, size); }}Copy the codeHeap sort
Based on the above statement, an unordered array or list will be constructed into a large root heap. The largest element in the List is always in the root node List[0], and by interchanging it with List[n-1], we can place that element in the correct order. At this time. If we remove List[n-1] from the large root heap (which can be done by reducing the size of the large root heap), the remaining nodes, the children of the original root, List[1]… List[n-2] is still the large root heap. The new List[0] node may violate the properties of the large root heap, so maxHeapify(0, size-1) is applied to reconstruct a large root heap on List[0,… n-1]. Repeat this process until the heap size drops to 1. At this point, the elements in the list are already sorted.
Time complexity The time complexity of heap sort is O(nlogn), O(n) times maxHeapify is called, and the time complexity of each call maxHeapify is O(logn).
code
/** * Heap sort time complexity O(nlogn) */
public void heapSort(a) {
buildMaxHeap();
for (int i = list.size() - 1; i >= 1; i--) {
swap(0, i);
maxHeapify(0, i); }}Copy the codePriority queue
Based on binary heap, there is a very common application: priority queue. Here, we focus on how to implement the maximum priority queue based on the maximum heap. Here is the definition of a priority queue. A priority queue is a data structure used to maintain a set S composed of a group of elements, each of which has an associated value, called a keyword. A maximum priority queue supports the following operations:
- IncreaseKey(S,x,k): Increase the keyword value of element x to k while maintaining the large root heap nature (maximum priority queue). This assumes that the value of k is not less than the original keyword value of x.
- Insert(S, x): Inserts the element X into the set S while maintaining the large root heap nature (maximum priority queue).
- Maximum(S): Returns the element in S with the largest keyword (highest priority).
- ExtractMax(S): Removes and returns the element in S with the largest keyword (highest priority).
increaseKey
The increaseKey operation increases the keyword value of the List[I] element, which may violate the maximum heap property relative to its parent. Once a destructive value is found, float up. Because if you float up, you can still violate the maximum heap property. This process, then, needs to be repeated. Time complexity: O(logn).
/** * To raise the value of the node element subscript I to key, ensure that list.get(I) < key */
private void increaseKey(int i, int key) {
if (key < list.get(i)) {
throw new UnsupportedOperationException("new key should be larger than the current key");
}
list.set(i, key);
while (i > 0&& list.get(getParentIndex(i)) < list.get(i)) { swap(i, getParentIndex(i)); i = getParentIndex(i); }}private void swap(int i, int j) {
int temp = list.get(i);
list.set(i, list.get(j));
list.set(j, temp);
}
Copy the codeinsert
Insert adds an element to the priority queue and maintains the nature of the large root heap (maximum priority queue). Here we implement this functionality based on the increaseKey operation. It’s simple: add a MIN_VALUE element to the end of the large root heap list, and then increaseKey its value to the specified element value. Time complexity: O(logn).
Public void insert(int val) {list.add(integer.min_value); public void insert(int val) {list.add(integer.min_value); increaseKey(list.size() - 1, val); }Copy the codemaximum
This is easier, we simply return List[0] which is the largest element in the large root heap, the highest priority element in the maximum priority queue. Time complexity: O(1)
public int peekMax() {
if (list.size() < 1) {
throw new UnsupportedOperationException("size of maxHeap is less than 1~");
}
return list.get(0);
}
Copy the codeextractMax
List[0] is exchanged with List[n-1], List[n-1] is removed from the List, and maxHeapify is applied to List[0]. Time complexity: O(logn).
public int popMax() {
if (list.size() < 1) {
throw new UnsupportedOperationException("size of maxHeap is less than 1~");
}
int max = list.get(0);
swap(0, list.size() - 1);
list.remove(list.size() - 1);
maxHeapify(0, list.size());
return max;
}
Copy the codeThe complete code
If list[0,...,n-1] represents a complete binary tree, then the internal relationship between the subscripts of parent node list and child node list is as follows: * For any subscript node I: * (1) Parent node: I == 0? Null: (I - 1) / 2 * (2) the left child: I + 2 * 1 * right child: 2 * I * < p > * 2 + 2. Large root heap definition: the value of the parent node >= the value of its child node * list(I) >= list(2* I +1) && list(I) >= list(2* I +2) * small root heap definition the same * * 3. Max heap build heap, according to the properties of full binary tree, the number of leaf nodes than internal nodes 1, so n/ 2-1-0 maxHeapify */
public class MaxHeap {
private List<Integer> list;
public MaxHeap(List<Integer> list) {
this.list = new ArrayList<>(list);
}
/** * Heap sort time complexity O(nlogn) */
public void heapSort(a) {
buildMaxHeap();
for (int i = list.size() - 1; i >= 1; i--) {
swap(0, i);
maxHeapify(0, i); }}/** * build a large root heap, linear time complexity O(n) */
public void buildMaxHeap(a) {
int size = list.size();
for (int i = size / 2 - 1; i >= 0; i--) { maxHeapify(i, size); }}/** * maxHeapify from a node with subscript root, time complexity O(logn) */
private void maxHeapify(int root, int size) {
int left = getLeftChildIndex(root);
int right = getRightChildIndex(root);
int max = root;
if (left < size && list.get(left) > list.get(root)) {
max = left;
}
if (right < size && list.get(right) > list.get(max)) {
max = right;
}
if (root != max) {
swap(root, max);
maxHeapify(max, size);
}
}
public int popMax(a) {
if (list.size() < 1) {
throw new UnsupportedOperationException("size of maxHeap is less than 1~");
}
int max = list.get(0);
swap(0, list.size() - 1);
list.remove(list.size() - 1);
maxHeapify(0, list.size());
return max;
}
public int peekMax(a) {
if (list.size() < 1) {
throw new UnsupportedOperationException("size of maxHeap is less than 1~");
}
return list.get(0);
}
/** * To raise the value of the node element subscript I to key, ensure that list.get(I) < key */
private void increaseKey(int i, int key) {
if (key < list.get(i)) {
throw new UnsupportedOperationException("new key should be larger than the current key");
}
list.set(i, key);
while (i > 0&& list.get(getParentIndex(i)) < list.get(i)) { swap(i, getParentIndex(i)); i = getParentIndex(i); }}private void swap(int i, int j) {
int temp = list.get(i);
list.set(i, list.get(j));
list.set(j, temp);
}
/** * Big root inserts an element and maintains the big root heap attribute */
public void insert(int val) {
list.add(Integer.MIN_VALUE);
increaseKey(list.size() - 1, val);
}
private int getLeftChildIndex(int root) {
return root * 2 + 1;
}
private int getRightChildIndex(int root) {
return root * 2 + 2;
}
private int getParentIndex(int root) {
if (root == 0) {
throw new UnsupportedOperationException("0 doest't have a parent node");
}
return (root - 1) / 2;
}
public List<Integer> getList(a) {
returnlist; }}Copy the codeSome test cases
@Test
public void testCase01() {
List<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 5, 4));
MaxHeap maxHeap = new MaxHeap(list);
maxHeap.heapSort();
System.out.println(maxHeap.getList()); // 1, 3, 4, 5
}
@Test
public void testCase02() {
List<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 5, 4, 2));
MaxHeap maxHeap = new MaxHeap(list);
maxHeap.buildMaxHeap();
int max = maxHeap.popMax();
System.out.println(max); // 5
System.out.println(maxHeap.getList()); // 4, 2, 3, 1
}
@Test
public void testCase03() { List<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 5, 4)); MaxHeap maxHeap = new MaxHeap(list); maxHeap.buildMaxHeap(); maxHeap.insert(11); System.out.println(maxHeap.getList()); // 11, 5, 3, 1, 4}Copy the codeJava PriorityQueue PriorityQueue
The JDK tool class already has the PriorityQueue we implemented above: PriorityQueue.
- PriorityQueue is an unbounded queue based on a binary heap implementation
- PriorityQueue supports either default natural order or custom sort logic
- PriorityQueue does not allow null values and does not support non-Comparable objects, such as user-defined classes. Priority queues require that objects be sorted using the Java Comparable and Comparator interfaces, and that elements are treated by priority when sorted.
- PriorityQueue is non-thread-safe, so Java provides PriorityBlockingQueue (implementing the BlockingQueue interface) for Java multithreaded environments.
Here is a Demo that shows that this PriorityQueue is similar to the PriorityQueue function I implemented above. So far, we’ve written a priority queue in the JDK source code by hand.
public static void main(String[] args) {
Queue<Integer> queue1 = new PriorityQueue<Integer>();
queue1.add(2);
queue1.add(1);
queue1.add(3);
while(! queue1.isEmpty()) { Integer i = queue1.poll(); System.out.println(i); } Comparator<Student> comparator = Comparator.comparingInt(o -> o.id); Queue<Student> queue2 =new PriorityQueue<Student>(comparator);
queue2.add(new Student(2."B"));
queue2.add(new Student(1."A"));
queue2.add(new Student(3."C"));
while (!queue2.isEmpty()) {
Student s = queue2.poll();
System.out.println(s.toString());
}
}
public static class Student {
private int id;
private String name;
public Student(int id, String name) {
this.id = id;
this.name = name;
}
public String toString(a) {
return id + "-"+ name; }}Copy the codeRefer to the link
- www.jianshu.com/p/c577796e5…
- www.itcodemonkey.com/article/866…
- Introduction to algorithms chapter 6, heap sort related content
- baike.baidu.com/item/ complete binary tree