Hello everyone. We’re going to learn Chapter 5 Binary Tree of Data Structure and Algorithm.
Today we’re going to introduce an important data structure, heap
and the relationship between heap and priority queue.
We take min heap for example to introduce heap.
Min heap is such a sequence of keys.
In this sequence, the i-th element is smaller than or equal to
the 2i+1-th element and 2i+2-th element.
We can draw it as a complete binary tree
and we can see in the tree the key of a node
is smaller than the keys of its left and right
children. Of course they can be equal.
Similarly, we can define max heap. Heap is in fact the
hierarchical sequence of complete binary tree. So we can use array to store it.
The constraint in heap is quite
loose, the main constraint is constraint between father and son.
However, there is no constraint between siblings.
Therefore, the heap is not unique, that is for a group of numbers,
we can construct different max heaps using these numbers. Of course, the common property of these heaps
is the key of root is the smallest in the subtree.
Logically, we can see the heap is
a tree and, more specifically, is a complete binary tree.
So we can use an array to implement it.
Therefore, there is an array to store the elements, a variable to specify the maximum number of elements
the array can store and the number of elements currently in the heap.
As a data structure, we always define insertion, deletion, query and modification
on it. And as an binary tree, we should define
method to find the left and right child of a node and the father of a node. A very indispensable method
in the heap is to delete the minimum element in the heap, because it’s easy for us to find
the minimum element in the heap, but it’s easy to find the maximum element in the max heap.
After finding it, it will be dispatched to a serving queue,
that is it’s now out, and it’s a common case using a priority queue.
There are 2 very import method named SiftUp and SiftDown.
They are similar to push and pop in stack and queue.
They are very basic method, let’s see the process of
SiftDown in min heap.
For it’s a min heap, we
can suppose that in the subtree of root 72,
its left subtree and right subtree
are both min heaps.
Then we can use the method SiftDown, that is find the smaller one out of two child nodes
and change positions of the node and the smaller child node.
And we go into the subtree and repeat the same process
until the node is put in a proper position. The position may not be position of some leaf,
it may be the original position, or some position.
The algorithm shown is the SiftDown method.
We have emphasize before that SiftDown is method on a subtree, so we don’t always start
from node with label 0 but from position.
At first, we assign the value position to i,
and assign the label of the left child to j.
We save the value of the father node first, and in the following steps,
we find the smaller child node of node i first,
and because we have already assigned the label of left child to j,
so if the value of node j+1 is smaller than
that of node j, then j++.
Then we compare the value of
the node at position
to the smaller child node, that is
if the value of child is smaller, we should move it
up to the position of its father.
That is in fact equal to SiftDown the father node.
And the next label which is going to be processed is
in the next level of the tree, including the label of the current node
and the label of its left child node. And we repeat the process.
So when can we stop the process? That is when the node is
bigger than its two child nodes
Or there is no position
to SiftDown
So we stop at position i, so we put
the value we saved before to position i.
So actually there are some differences between the method SiftDown and exchange process shown
in the animation before, for that the SiftDown is actually a process from position to
some position, and it exchange adjacent node in the sequence.
So we can find the bottom position and move up every node
and at last we put the node at the first position
to the target position. Similarly, we can implement method SiftUp
to move a node up. This is simpler than SiftDown.
Because it’s easy to find the father node of a node.
for that a node only has one father node. When the
value of father node is bigger than that of the node in the min heap,
we should SiftUp the node.
Let’s see the process of
establishing a min heap. These N
elements is as what you input.
Then we put them in an array
and then adjust them. We have to ways to think how to establish a heap.
We can adjust from the top to bottom.
This is not easy, for
the constraint is every node should be
smaller than or equal to its children. However, it’s not easy
to adjust nodes in the bottom to meet the constraint. But if we adjust from the bottom to top,
it’s very easy, for there are half of nodes forming a heap already.
And we’re going to find the first node
with children, and adjust it with its children
to form a sub heap. We can do this kind of thing from the about half position
to the root, and the step-by-step adjustment
to establish such a min heap.
Well, let’s look at this example.
68, 05, 16 and 94 are not needed to be adjusted. And 23
is already a sub heap. And 71 is adjusted together with the smaller value, 05.
And we’re going to adjust 73, it’s a similar process.
it’s a result of continuously SiftDown.
And finally we’re going to adjust the root. For its two subtree is already sub heaps,
we can conveniently SiftDown the root
and make the structure min heap.
Let’s see
the code. The code is actually very easy,
we adjust from half position to the root.
For each adjustment, we SiftDown the node,
and then we finish it.
And for the insertion process, it’s also very easy. For insertion we should consider that
we cannot insert a value to a random position, so we usually
insert to the position
behind the last element. For that position is in the leaf level, is that position
a legal position in the heap? We should compare it with its father node,
this is a process of SiftUp. We adjust it until
it’s at a proper position, this is the code of this algorithm.
Let’s see the more complex process of deleting an element in a min heap.
We delete some element at given position.
If the given position is legal, we first
exchange the element with the last element in the heap,
that is exchange the position with the last element.
And after we exchange these elements, we’re going to see whether
the element there need SiftUp or SiftDown.
Actually, rather SiftDown or SiftUp is executed in the heap.
Well, let’s see such an example. In this heap, we want to
delete 68. This is a min heap, and first we replace it with the last element 45.
And we should make a decision that whether it needs SiftDown or SiftUp, and obviously it needs SiftUp.
And we finish the adjustment after SiftUp. Obviously, if SiftUp we don’t need SiftDown.
Next, we’re going to delete 16, we replace 16 with 45,
and we can see it needs SiftDown.
we exchange it with
the root of the subtree and examine whether we should continue SiftDown, we have finished for we have already down to leaf.
It’s very efficient to construct a heap for
half of n elements in the heap don’t need to be moved.
And quarter of elements need to be moved only once
And the number of elements reduces by half when we go up a level,
and the times of that we move the elements in that level is only increased by 1.
Thus, the total times of that we move the elements
is such a number.
The number is order of O(n). For n
elements, the elements may be out of order, but we can construct
a heap in linear time. It’s very efficient.
For the height of the heap is log n
and insertion and deletion only work on part of the heap,
that is they only affect elements in path of
the element to the root or the element to some leaf
and do some exchanges in that path.
The times of exchange is not more than the height of the tree, so the time complexity is log n.
The heap can be used to implement the priority queue. And we can see it is used in many applications
such as operating system. We should maintain the priority of processes and we should do some job arrangement.
When we maintain a priority queue, actually in many situations
we only care who is the biggest one or smallest one and this one should be served first.
There is other way to implement the priority queue. It is not only can be implemented by heap.
And if we should modify the priority of some element in the priority queue
we need some auxiliary data structure to do some index, then we can find it, modify it and adjust the queue.
Here are some questions. In the previous animation pf
SiftDown, we exchange the inverse pair
immediately we find it. But when we implement it by code, we don’t need to exchange every time.
We first move the element to be adjusted to a temporary variable and
begin SiftDown. In the process we actually
just push up every element and when we get to the target position
we put the saved element to the position.
How can we rewrite the code? And another question is can we
maintain maximum element and minimum element together in one data structure? Actually there is a data structure named
min-max heap that can do this. Thank you all.