The heap is a binary tree implemented with an array, so it does not use parent or child pointers. The heap is sorted according to the "heap attribute", which determines the position of the node in the tree.
Commonly used methods of heap:
- Build priority queue
- Supports heap sorting
- Quickly find the minimum (or maximum) value in a set
- Show off in front of friends
Heap attributes
There are two types of heaps:max heapandmin heap, the difference between the two lies in the way the nodes are sorted.
In a max-heap, the value of the parent node is greater than the value of each child node. In a min-heap, the value of the parent node is smaller than the value of each child node. This is the so-called "heap property", and this property is true for every node in the heap.
example:
Figure 1 Heap
This is a max-heap, because the value of each parent node is greater than the value of its child nodes.10 Compare 7 and 2 All big.7 Compare 5 and 1All big.
According to this property, the max heap always stores the maximum value at the root node of the tree. For a min-heap, the element in the root node is always the smallest value in the tree. The heap attribute is very useful because the heap is often used as a priority queue because the "most important" elements can be accessed quickly.
**Note:** The root node of the heap stores the largest or smallest element, but the sorting order of other nodes is unknown. For example, in a max-heap, the largest element is always located at index 0, but the smallest element is not necessarily the last element. --The only thing that can be guaranteed is that the smallest element is a leaf node, but it is not sure which one.
The difference between a heap and an ordinary tree
The heap does not replace the binary search tree. There are similarities and some differences between them. Let’s take a look at the main differences between the two:
**The order of nodes. **In a binary search tree, the left child node must be smaller than the parent node, and the right child node must be larger than the parent node. But this is not the case in the heap. In a max-heap both child nodes must be smaller than the parent node, while in a min-heap they both must be larger than the parent node.
**Memory usage. **Normal trees take up more memory space than the data they store. You must allocate memory for the node object and the left/right child node pointers. The heap only uses a data to store an array and does not use pointers.
balance.A binary search tree must be "balanced" so that the complexity of most of its operations can be achievedO(log n). You can insert/delete data in any order, or use an AVL tree or a red-black tree, but the entire tree doesn't actually need to be ordered in a heap. We only need to satisfy the heap properties, so balancing in the heap is not a problem. Because the data in the heap is organized in a way that ensuresO(log n) performance.
**search. **Searching in a binary tree will be fast, but searching in a heap will be slow. Searching in the heap is not the first priority, because the purpose of using the heap is to put the largest (or smallest) node at the front so that related insertion and deletion operations can be quickly performed.
tree from array
Using arrays to implement tree-related data structures may seem a bit odd, but it is very efficient in both time and space.
We are going to store the tree in the above example like this:
[ 10, 7, 2, 5, 1 ]
That’s all! We don't need any extra space other than a simple array.
If we are not allowed to use pointers, then how do we know which node is the parent node and which node is its child node? Good question! There is a mapping relationship between the position index of a node in the array and the index of its parent node and child node.
if i is the index of the node, then the following formula gives the position of its parent node and child node in the array:
parent(i) = floor((i - 1)/2)
left(i) = 2i + 1
right(i) = 2i + 2
Notice right(i) It's simple left(i) + 1. The left and right nodes are always in adjacent positions.
Let's put the written formula into the previous example and verify it.
| Node | Array index (i) | Parent index | Left child | Right child |
|---|---|---|---|---|
| 10 | 0 | -1 | 1 | 2 |
| 7 | 1 | 0 | 3 | 4 |
| 2 | 2 | 0 | 5 | 6 |
| 5 | 3 | 1 | 7 | 8 |
| 1 | 4 | 1 | 9 | 10 |
**Note:**Root node
(10)There is no parent node because-1is not a valid array index. Likewise, nodes(2)，(5)and(1)There are no child nodes because these indexes have exceeded the size of the array, so we need to ensure that they are valid index values when using these index values.
To review, in a max-heap, the value of a parent node is always greater than (or equal to) the value of its child node. This means that the following formula for any index in the array iAll are established:
array[parent(i)] >= array[i]
You can use the above example to verify this heap attribute.
As you can see, these formulas allow us to find the parent or child nodes of any node without using pointers. Things are more complicated than simply getting rid of pointers, but here's the deal: we save space, but do more computation. Fortunately these calculations are fast and only take **O(1)** time.
It is important to understand the relationship between array indexing and node position. Here is a larger heap with 15 nodes divided into 4 levels:
Figure 2 Heap layered into four layers
Figure 3 Heap layered into four layers
The number in the picture is not the value of the node, but the index of the array that stores this node! Here is the relationship between array indexes and tree levels:
Figure 4 The relationship between index and hierarchy
As you can see from the picture above, the parent node is always in front of the child node in the array.
Note that this scheme comes with some limitations. You can organize data as follows in a normal binary tree, but not in a heap:
Figure 5 The relationship between index and hierarchy
In a heap, filling in the next level is not allowed until all nodes in the current level have been filled, so the heap always has this shape:
Figure 6 Shape of the pile
**Note:** You can use a normal tree to simulate a heap, but that is a huge waste of space.
Quick quiz, suppose we have an array like this:
[ 10, 14, 25, 33, 81, 82, 99 ]
Is this a valid heap? The answer is yes! An array ordered from low to high is an effective minimum heap. We can draw this heap:
Figure 7 Heap
The heap attribute applies to every node because the parent node is always smaller than its byte size. (You can also verify this: an array ordered from high to low is a valid max heap)
**Note:** Not every min-heap is an ordered array! To convert a heap into an ordered array, you need to use heap sort.
More mathematical formulas
If you're curious, here are some more formulas describing some of the definite properties of the heap. You don't need to know these, but they can come in handy sometimes. You can skip this part directly!
treehighIt refers to the number of steps required to go from the root node of the tree to the lowest leaf node, or more formally defined: height refers to the maximum value of the edge between nodes. A heap of height h has h+1 levels.
The height of the following heap is 3, so it has 4 levels:
Figure 8 Heap
If a heap has n nodes, then its height is h = floor(log2(n)). This is because we always have to fill this layer completely before filling in a new layer. The example above has 15 nodes, so its height is floor(log2(15)) = floor(3.91) = 3。
If the bottom layer is filled, then that layer contains 2^h nodes. The number of nodes above this level in the tree is 2^h - 1. In the same example above, the bottom layer has 8 nodes, which is actually 2^3 = 8. The first three layers contain a total of 7 nodes, namely:2^3 - 1 = 8 - 1 = 7。
So the number of nodes in the entire heap is: * 2^(h+1) - 1*. In the above example,2^4 - 1 = 16 - 1 = 15
Leaf nodes are always located at the end of the array floor(n/2) and n-1 between.
What can be done with a heap?
There are two primitive operations used to ensure that the heap is a valid max-heap or min-heap after inserting or deleting a node:
shiftUp(): If a node is larger (max heap) or smaller (min heap) than its parent node, then it needs to swap positions with the parent node. This causes the node's position in the array to rise.shiftDown(): If a node is smaller (max-heap) or larger (min-heap) than its child nodes, then it needs to be moved down. This operation is also called "heapify".
shiftUp or shiftDown is a recursive process, so its time complexity is O(log n)。
There are some other operations based on these two primitive operations:
insert(value): Add a new element to the end of the heap, then useshiftUpto fix the pair.remove(): Remove and return the maximum value (max-heap) or minimum value (min-heap). In order to fill the vacancy after deleting this node, you need to move the last element to the position of the root node, and then useshiftDownMethod to repair the heap.removeAtIndex(index): andremove()Same, the difference is that you can remove any node in the heap, not just the root node. Used when it is out of order when comparing positions with child nodesshiftDown(), used if compared with the parent node and found to be out of order.shiftUp()。replace(index, value): Assign a smaller value (min heap) or a larger value (max heap) to a node. Since this operation destroys the heap attributes, you need to useshiftUp()to fix the heap properties.
The time complexity of all the above operations is O(log n), because both shiftUp and shiftDown are time-consuming. There are a few operations that take more time:
search(value):The heap is not built for fast searching, butreplace()andremoveAtIndex()The operation requires finding the index of the node in the array, so you need to find this index first. Time complexity:O(n)。buildHeap(array):by calling repeatedlyinsert()Method converts an (unordered) array into a heap. If you are smart enough, you can O(n) Completed within time.- Heap sort: Since a heap is an array, we can use its unique properties to sort the array from low to high. Time complexity:O(n lg n)。
There is another one in the pile peek() Method, returns the maximum value (max heap) or minimum value (min heap) without deleting the node. time complexity O(1) 。
Notice:So far, common operations on the heap still use
insert()Insert a new element, and passremove()Remove the maximum or minimum value. The time complexity of both isO(log n). Other operations are used to support more advanced applications, such as establishing a priority queue.
insert
Let's take a look at the details of the insertion operation through an insertion example. We will number 16 Insert into this heap:
Figure 9 Heap
The array of heap is: [ 10, 7, 2, 5, 1 ]。
The first pass inserts a new element into the end of the array. The array becomes:
[ 10, 7, 2, 5, 1, 16 ]
The corresponding tree becomes:
Figure 10 Heap
16 The first empty position of the last row is added.
What doesn't work is that now the heap attributes are not satisfied because 2 exist 16 on top, we need to place the big numbers on top (this is a max heap)
To restore the heap properties we need to swap 16 and 2。
Figure 11 Heap
It's not finished yet because 10 than 16 Small. We continue swapping our inserted element and its parent until its parent is larger than it or we reach the top of the tree. this is what is called shift-up, required after every insertion operation. It "floats" a number that is too large or too small to the top of the tree.
Finally we get the heap:
Figure 12 Heap
Delete root node
We will put the (10) Delete:
Figure 13 Heap node deletion
Now there is an empty node at the top, what should I do?
Figure 14 Heap node deletion
When inserting a node, we return the new value at the end of the array. Now we do the opposite: we take the last element in the array, put it at the top of the tree, and then fix the heap properties.
Figure 15 Heap node deletion
Now let’s see what shift-down (1). To maintain the heap properties of a max-heap, we need the top of the tree to be the largest data. There are now two numbers available for swapping 7 and 2. We choose the larger of the two called the maximum and place it at the top of the tree, so swap 7 and 1, now the tree becomes:
Figure 16 Heap node deletion
Continue heaping until the node has no children or it is larger than both children. For our heap, we only need one more swap to restore the heap properties:
Figure 17 Heap node deletion
Delete any node
Most of the time what you need to delete is the root node of the heap, because that's what the heap is designed for.
However, it is also useful to delete arbitrary nodes. This is remove() A common version of shiftDown and shiftUp。
Let’s still use the previous example and delete (7):
[Image upload failed...(image-d46ac4-1534077058042)]
The corresponding array is
[ 10, 7, 2, 5, 1 ]
You know that removing an element destroys the max-heap or min-heap properties. We need to swap the deleted element with the last element:
[ 10, 1, 2, 5, 7 ]
The last element is the element we need to return; then call removeLast() to delete it. (1) is smaller than its child nodes, so it needs shiftDown() to repair.
However, shift down is not the only case we have to deal with. It's also possible that we need to shift up. Consider removing from the heap below (5) What happens:
Figure 18 Heap node deletion
now (5) and (8) Exchanged. because (8) is larger than its parent node, we need shiftUp()。