Today we will learn about the new data structure - heap.
01Definitions
A heap is a special kind of binary tree and satisfies the following two properties:
（1）heap upIt's a tree.complete binary tree (math.)；
（2）heap upAny of the node element values inless than or equal to(orgreater than or equal to) aroundsubtreeAll node element values in the
A small root heap where the root node element is always the minimum value, i.e., each node element value in the heap is less than or equal to all node element values in the left and right subtrees;
Large root heap where the root node element is always the maximum value, i.e., each node element value in the heap is greater than or equal to all node element values in the left and right subtrees;
According to the definition of the heap, it is easy to find that the heap is particularly suitable for the collection of the most value, as well as to find the most value of the derived problems such as: sorting, priority queuing, dynamic ranking, etc.
02Structure
We specify that the heap is a special kind of fully binary tree, so the logical structure of the heap is a tree.
We specified two storage structures for trees, sequential storage (arrays) and chained storage (linked lists), so what is the storage structure of the heap?
Since the heap is a fully binary tree, the tree storage structure is of course applicable to the heap. But the heap is generally chosen sequential storage (array) implementation. There are three reasons for this:
（1）Simple location calculation: An array implementation of a heap can use the full binary tree feature to represent the indexing relationship of parent and child nodes using a simple mathematical formula, thus avoiding the use of additional pointers for a chained table implementation, i.e., reducing memory overhead and implementation complexity;
（2）good performance: The contiguous memory nature of arrays allows for efficient access speeds, whereas linked lists have relatively poor access speeds because the nodes are not necessarily contiguous;
（3）easy operation: The array implementation is simpler and more efficient in logical implementation, by exchanging elements in the array can quickly realize the nature of the heap, the chain table implementation in the insertion and deletion operations need to traverse the chain table efficiency is far less than the array implementation;
Summarize a sentence array simple, continuous memory, better performance, so the general choice of array implementation of the heap, of course, not the general case can also be implemented using the chain table.
03, realization (minimal heap)
Below we will use the array to implement a minimum heap structure, the maximum heap is just a comparison of the size of the different here will not do too much elaboration.
1、Initialization Init
First we need to define two private variables, one to hold the array of heap elements and one to hold the index of the last element of the array, which is mainly used to keep track of the current number of heap elements.
And the initialization method is to initialize two variables, create an array of the specified capacity, and mark the index of the tail element of the array as -1, indicating that there are no elements in the heap yet.
// Store the heap elements
private int[] _array;
// index of the tail element of the array
private int _tailIndex;
//Initialize the heap to the specified capacity
public MyselfMinHeap Init(int capacity)
{
//Initialize an array of the specified length to hold the heap elements
_array = new int[capacity]; //Initialize the array to the specified capacity.
//Initialize the index of the tail element of the array to -1, indicating that the empty array
_tailIndex = -1;
// Return to the heap
return this; }
}
2、Get the heap capacity Capacity
Heap capacity refers to the fixed space of an array, i.e., the maximum number of elements the array can hold, and it is straightforward to return the length of the array.
//stack capacity
public int Capacity
{
get
{
return _array.Length;
}
}
3、Get the number of heap elements Count
The number of heap elements refers to the total number of elements in the current heap, which we can get by adding 1 to the index value of the tail element of the private field array.
//heap element number
public int Count
{
get
{
//Array tail element index plus 1 is the number of heap elements
return _tailIndex + 1;
}
}
4、Get the top element of the heap Top
The top element of the heap refers to the root node of the tree node, which is the first element in the array. Also be careful to determine whether the array is empty, for empty report an exception.
//get the top element of the heap, that is, the smallest element
public int Top
{
get
{
if (IsEmpty())
{
// Empty heap, do not get the smallest heap element.
throw new InvalidOperationException("Empty Heap");
}
return _array[0];
}
}
5, whether the empty pile IsEmpty
Empty heap means there is no element in the heap yet, when the index of the end element of the array is -1 it means empty heap.
//check whether the heap is empty
public bool IsEmpty()
{
return _tailIndex == -1;
}
6. Whether the heap is full IsFull
Full heap means that the heap space is full and no new elements can be added, when the index of the last element of the array is equal to the capacity of the array minus 1, it means that the heap is full.
//check whether the heap is full
public bool IsFull()
{
//The index of the last element of the array is equal to the capacity of the array minus 1 means that the full heap
return _tailIndex == _array.Length - 1;
}
7、Into the pile Push
Into the heap means adding a new element to the heap.
And getting into the heap also involves the question of how to preserve the properties of the heap after each new element is added. Obviously there's no way we can do that either by directly inserting the new element directly into its correct position, so we can sort out the process of adding a new element, which might be roughly the following steps:
(1) First add the new element to the end of the heap;
(2) The heap is then adjusted so that it satisfies the properties of a heap;
(3) Update the index of the end-of-heap element;
And the hard part is obviously in the second step, how do you adjust the array so that it satisfies the properties of a heap?
Let's start by directly simulating pushing 7654 into the heap in sequence and see how that works.
(1) First 7 is entered into the heap, at this point there is only one element, no need to do any operation, and 7 is used as the root node;
(2) Then 6 into the heap, at this time there are already two elements, so you need to maintain two properties of the heap: the root node is always the smallest element and the heap is a complete binary tree. By the complete binary tree characteristics, the root node left child node index is 20+1=1 and the right child node index is 20+2=2, and at this time the index of 6 is 1, so 6 is the left child node; and because 6 is smaller than 7, the root node becomes 6, and 7 becomes the left child node of the root node;
(3) Then 5 is added to the heap, at this point there are already 3 elements, so the index of 5 is 2, and the index of the right child of the root node is 2*0+2=2, so 5 is added as the right child of the root node. 5 is smaller than 6, so 5 and 6 interact with each other in position;
(4) then 4 into the heap, at this time there have been 4 elements, so the index of 4 is 3, and 7 node left child node index is 2 * 1 + 1 = 3, so 4 is added as the left child node of the 7 node. 4 is smaller than 7, so 4 and 7 interact position; again compare 4 and 5, 4 is smaller than 5, so 4 and 5 interact position;
I believe that by now you have seen a bit of a pattern, adjust the entire array elements to make it meet the nature of the heap of the entire process is roughly divided into the following steps:
(1) Compare the size of its value with that of its parent element starting from the new element upwards;
(2) If the new element value is less than its parent node element value, then interact both positions, otherwise end the adjustment;
(3) Repeat the above steps until the root node is processed.
The code is implemented as follows:
// into the heap to add an element to the heap
public void Push(int data)
{
if (IsFull())
{
// The heap is full, you can't add an element to it.
throw new InvalidOperationException("Full pile");
}
// New element index
var index = _tailIndex + 1; //Add the new element index to the end of the array.
// Add the new element at the end of the array
_array[index] = data;
// Sift up the heap to maintain the nature of the heap
SiftUp(index);
//advance the index of the tail element backward by 1 bit
_tailIndex++;
}
// Adjust the heap upwards to maintain the nature of the heap
private void SiftUp(int index)
{
// Keep adjusting the heap until it reaches the top of the heap
while (index > 0)
{
// Calculate the index of the parent element
var parentIndex = (index - 1) / 2; // If the current element is greater than or equal to its parent, end the adjustment.
//If the current element is greater than or equal to its parent, end the adjustment
if (_array[index] >= _array[parentIndex])
{
break;
}
// Otherwise, swap the two elements
(_array[parentIndex], _array[index]) = (_array[index], _array[parentIndex]);
// Update the current index to the parent element index to continue the adjustment
index = parentIndex;
}
}
8, out of the pile Pop
Out of the heap means removing and returning the top element of the heap (the smallest element in the heap).
And going out of the heap similarly involves the same problem as going into the heap, that is, how to preserve the characteristics of the heap after each deletion of an element.
Obviously deleting and adding elements are not yet the same. Adding a new element is still a full binary tree, except that it may not satisfy the properties of a heap, so it needs to be adjusted. Deletion is different. Imagine what happens when we delete the top element of the heap. The root node is empty, at this point can still be more complete binary tree? Obviously not.
How to deal with it? The intuitive idea is that the root node is empty with its children nodes to supplement on the chant, so from top to bottom has been filled, until the last empty fall in the leaf nodes of the layer, if the empty space fell to the left side of the leaf nodes, and the right side of the value, at this time, it is shown that the heap does not satisfy the characteristics of the complete binary tree, and therefore need to be moved to the end of the heap of the empty space, imagine the head is big. This is obviously not a good way.
Since we finally want to move the root node after the deletion of this empty space to the end of the heap, why not directly this empty space and the tail element of the heap directly swap a position, and then refer out of the heap to adjust the entire array so that it meets the nature of the heap.
As we sort through the whole process, there may be roughly the following steps:
(1) First get the top element of the heap and store it temporarily;
(2) Assign the tail element of the heap to the top element of the heap and leave the tail element of the heap empty;
(3) The heap is then adjusted so that it satisfies the heap property;
(4) Updates the index of the tail element of the array and returns the temporary top-of-heap element;
And the difficulty is also in the second step, how to adjust the array so that it meets the properties of the heap? Into the heap is the new element at the end of the heap so it is adjusted from bottom to top, while out of the heap is the top element needs to be adjusted can it be adjusted from top to bottom?
Let's push 4 out of the heap after pushing 87654 into the heap in order and see how that works.
First delete the root node 4 and put the heap tail element 8 to the root node;
To maintain the heap property, find the smallest element in the root node and its children and interact the position with the current root node 8, because 8>6>5, so 5 interacts the position with 8;
The 8 node then continues to compare with its children as 8>7,so 7 interacts with 8 in position.
This out-of-heap process we can summarize in the following steps:
(1) Starting from the current node, find the values of its child node elements;
(2) Compare the current node element value with the size of its child node element value, if the current node value is the smallest then end the adjustment, otherwise take the smallest value to interact with it;
(3) Repeat the above steps until the leaf node is processed.
The code is implemented as follows:
//Out of the heap Delete and return to the smallest element of the heap
public int Pop()
{
if (IsEmpty())
{
// Empty heap, can not be deleted and return to the smallest element of the heap operations
throw new InvalidOperationException("Empty heap");
}
// Remove the first element of the array that is the smallest element
var min = _array[0]; //Take out the first element of the array, i.e. the smallest element.
//Assign the last element of the array to the first element.
_array[0] = _array[_tailIndex]; //Assign the end element of the array to the first element.
//Set the end element of the array to the default value
_array[_tailIndex] = 0; //Assign the end element of the array to the first element.
//shift the index of the end element of the array forward by 1 bit
_tailIndex --;
//Shift down the heap to preserve the nature of the heap
SiftDown(0);
//return the smallest element
return min.
}
// Adjust the heap downward to maintain the nature of the heap
private void SiftDown(int index)
{
while (index <= _tailIndex)
{
// Define a smaller index variable to hold the smallest element to compare the current element and its left and right children.
var minIndex = index;
// Calculate the right child index
var rightChildIndex = 2 * index + 2; //Calculate the right child node index if it exists.
//If there is a right child node, compare it with the current element and keep the index with the smaller value
if (rightChildIndex <= _tailIndex && _array[rightChildIndex] < _array[minIndex])
{
minIndex = rightChildIndex;
}
// Calculate the left child index
var leftChildIndex = 2 * index + 1;
//If there is a left child node, compare it to the element with the smaller value and keep the index with the smaller value
if (leftChildIndex <= _tailIndex && _array[leftChildIndex] < _array[minIndex])
{
minIndex = leftChildIndex;
}
// If the current element is the smallest, stop the adjustment
if (minIndex == index)
{
break; }
}
//Otherwise, swap the current element and the smaller element
(_array[minIndex], _array[index]) = (_array[index], _array[minIndex]);
// Update the index to the smaller value index and continue adjusting
index = minIndex;
}
}
9. Heapify
Heapization means stacking an unordered array into a rootlet heap.
This can be done by calling out the heap is used to adjust the method. You can think about why not start adjusting at the end of the heap? Why is the downward adjustment method called from bottom to top?
//Heapify, i.e., heap an unordered array into a rootlet heap
public void Heapify(int[] array)
{
if (array == null || _array.Length < )
{
throw new InvalidOperationException("Invalid Array");;
}
// Copy the array to the heap
(array, _array, ); }
// Update the tail element index
_tailIndex = - 1;
// Adjust the heap downward from the last non-leaf node
for (int i = ( / 2) - 1; i >= 0; i--)
{
SiftDown(i);
}
}
classifier for sums of money: The test method code as well as the sample source code have been uploaded to the code repository for those who are interested./hugogoos/Planner