What is a Heap?
A heap is a special type of tree that needs to satisfy two requirements:
❝
- The heap is a complete binary tree
- The value of each node in the heap must be greater than or equal to (or less than or equal to) the value of each node in its child tree
❞
“First,” the heap must be a complete binary tree. What is a perfect binary tree? It means that the number of nodes in every layer is full except for the last layer, which is arranged to the left.
“Second,” the value of each node in the heap must be greater than or equal to (or less than or equal to) the value of each node in its child tree. In fact, we can put it another way: every node in the heap is greater than or equal to (or less than or equal to) the value of its left and right children.
A heap where each node is greater than or equal to the value of each node in the subtree is called a “big top heap”. A small top heap is a heap where the value of each node is less than or equal to the value of each node in the subtree.
The first and second are big top heaps, the third is small top heaps, and the fourth is not a heap. In addition, as you can see from the figure, we can build many different types of heap for the same set of data.
2. How to implement a heap
To implement a heap, we need to know what operations the heap supports and how to store a heap.
Full binary tree, more suitable for array storage. Using arrays to implement full binary trees is very space – saving. Because we don’t need to store Pointers to the left and right children, we can find the left and right children and the parent of a node simply by using the array’s subscript. In general, we see two implementations: the first one starts at 1, and the second one starts at 0.
2.1 subscripts start from 1
The structure is shown in the figure below
Can be seen from the diagram, the array subscript for node’s left child node I subscript is I < < 1, the right child nodes of the subscript is I < < | 1, the parent node is the subscript for I > > 1.
❝
- Left: I << 1 = I * 2
- Right: I < < 1 | 1 = I * 2 + 1
- Parent: I >> 1 = I / 2
- Leaf node: n / 2 + 1
❞
2.2 Subscripts start at 0
As you can see, the index of the left child of the node with subscript I is 2 times I + 1, the index of the right child is 2 times I + 2, and the parent is (I – 1) / 2.
❝
- Left: I * 2 + 1
- Right: I * 2 + 2
- Father :(i-1) / 2
- Leaves: n / 2
❞
3. Heap operation
The core operations of the heap are to insert an element into the heap and to delete the top element.
3.1. Insert an element into the heap
After inserting an element into the heap, we need to continue to satisfy the heap’s characteristics.
Usually we put the new element at the end of the heap to see if it still fits the characteristics of the heap, right? If not, we need to adjust the heap to meet the characteristics of the heap again, a process called heapify.
There are actually two kinds of heap, bottom up and top down. When you add a new element, you heap it from the bottom up.
Heapification is simply a matter of following the path of the nodes, comparing them up or down, and switching. The process is shown in the figure below:
As can be seen from the figure, compare the size of the newly inserted node with that of the parent node; If the child is less than or equal to the parent, we swap two nodes. Repeat the process until the two conditions above are met between the parent nodes.
3.2. Delete the heaptop element
From the second section of the heap definition, which states that every node has a value greater than or equal to (or less than or equal to) its children, we can see that the top element stores the maximum or minimum value of data in the heap.
Delete the top element, we usually do the same thing, not just delete it, but put the last node at the top of the heap, minus 1. Then use the same parent-child node comparison method, for the parent-child node does not meet the size of the relationship, the exchange of two child nodes; The process is repeated until the size relationship between the parent nodes is satisfied. That’s how you heap it from the top down. The process is as follows:
As can be seen from the figure above, since it is the last element that is removed and the “hole” in the tree will not appear in the heapification process, as shown in the figure below, the result of this heapification method must meet the characteristics of a complete binary tree.
The heap code implementation is as follows:
public class MaxHeap {
private final int[] heap;
private final int limit;
private int heapSize;
private final int startIndex;
public MaxHeap(int limit) {
this.limit = limit + 1;
heapSize = 1;
startIndex = 1;
heap = new int[this.limit];
}
public boolean isEmpty(a) {
return heapSize == startIndex;
}
public boolean isFull(a) {
return heapSize == limit;
}
public void push(int value) {
if (heapSize == limit) {
throw new RuntimeException("heap is full");
}
heap[heapSize] = value;
heapInsert(heap, heapSize++);
}
public int pop(a) {
int cur = heap[startIndex];
swap(heap, startIndex, --heapSize);
heapify(heap, startIndex, heapSize);
return cur;
}
/ * *
* Bottom-up
*
* @param arr
* @param index
* /
private void heapInsert(int[] arr, int index) {
int parent = parentIndex(index);
while (parent > 0 && arr[index] > arr[parentIndex(index)]) {
parent = parentIndex(index);
swap(arr, index, parent);
index = parent;
}
}
/ * *
* Top-down
*
* @param arr
* @param index
* @param heapSize
* /
private void heapify(int[] arr, int index, int heapSize) {
int left = leftIndex(index);
while (left < heapSize) {
int right = rightIndex(index);
// Get the maximum value of the left and right children
int largest = right < heapSize && arr[right] > arr[left] ? right : left;
// Compare the maximum value of the left and right child nodes with the index position
largest = arr[largest] > arr[index] ? largest : index;
// If neither child is older than your own, break out of the loop
if (largest == index) {
break;
}
Swap index and largest data
swap(arr, largest, index);
index = largest;
// Go to the next layer
left = leftIndex(index);
}
}
public int leftIndex(int index) {
return index << 1;
}
public int rightIndex(int index) {
return index << 1 | 1;
}
public int parentIndex(int index) {
return index >> 1;
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
MaxHeap maxHeap = new MaxHeap(7);
maxHeap.push(11);
maxHeap.push(7);
maxHeap.push(1);
maxHeap.push(9);
maxHeap.push(9);
maxHeap.push(13);
maxHeap.push(17);
System.out.println(maxHeap.pop());
System.out.println(maxHeap.pop());
System.out.println(maxHeap.pop());
System.out.println(maxHeap.pop());
System.out.println(maxHeap.pop());
System.out.println(maxHeap.pop());
System.out.println(maxHeap.pop());
}
}
Copy the codeA complete binary tree with n nodes, no higher than log base n. The heapification process is compared and exchanged along the path of nodes, so the time complexity of heapification is proportional to the height of the tree, that is, O(n∗log n). The primary logic for inserting data and removing heaptop elements is heapization, so the time complexity for both inserting an element and removing heaptop elements is O(n∗log n).
4, summary
A heap is a complete binary tree whose greatest property is that the value of each node is greater than or equal to (or less than or equal to) the value of its children. Therefore, heaps are divided into two categories, “big top heaps” and “small top heaps”.
The two most important operations in the heap are the insertion of a data and the deletion of a heaptop element, both of which use heapification. When we insert data, we put the newly inserted data at the end of the array and heap it from the bottom up; To delete the top of the heap, we place the last element of the array on the top of the heap and heap it from the top down. Both operations are O(n∗log n).