The properties of the heap
A heap is a completely binary tree, which can be implemented in reality through an array. One of its most important properties is that any node is smaller than (greater than) equals its child nodes. The heap with the smallest root node is called the smallest heap, and the heap with the largest root node is called the largest heap. The following figure shows an example of a largest heap and its array representation, which can be intuitively seen that each node is larger than its children.
As can be seen in the figure above, nodes of a completely binary tree can be arranged in order from the root node number 1, corresponding to the index in array A (note that the subscript here starts from 1). Given a node i, we can easily get its left child is 2i, right child is 2i+1, and parent node is i/2
Basic operations of heap
There are two basic operations for the heap (see the minimum heap as an example below):
Insert element k: add k directly to the end of the array, and then bubble up to adjust the heap. Bubble up operation: Compare the element to be adjusted to its parent node, and if it is greater than its parent node, exchange it until the properties of the heap are restored.
Extract the most value: the most value is the root element. Then delete it, let the root element = the last leaf node element, and then bubble-down from the root element to adjust the heap. Bubble down operation: Each time, you should select the smallest child node from the three nodes to adjust the node, which has the left and right children to exchange (if the smallest, it does not need to exchange itself), until the properties of the heap are restored.
In practice, it is often necessary to build an unordered array containing n elements into heaps. The constructor in the Heap class below will show how to build a heap through _bubbleDown bubble down adjustment. The heap is essentially a completely binary tree, and the tree height is always lognlogn. The time-consuming operation of each basic operation is to bubbling and adjust to meet the properties of the heap, so their time complexity is O(nlogn)O(nlogn).
Java example:
//Float public void swim(int k){ while(k/2>=1 && less(pq[k/2],pq[k])){ exch(pq,k/2,k); k=k/2; }}//Sink private void sink() { int k=1; while(2*k<N){ int j=2*k; if(less(pq[j],pq[j+1])) j++; if(less(pq[k],pq[j])) exch(pq,k,j); else break; k = j; }} Heap sorting implementation principle
It is divided into two steps:
1. Arrange arrays in binary heap order
2. Change the position of the root node and the last node, and then sink the root node.
accomplish:
Maybe my code is slightly different from the animation above, but the basic principles are similar.
public class HeapSort extends BaseSort { private int N; @Override public void sort(Comparable[] a) { N =a.length-1; int k = N/2; while(k>=1){ sink(a,k); k--; } k = 1; while(k<=N){ exch(a,k,N--); sink(a,k); } }}