Main Contents:
Basic concepts of heap, maximum heap, minimum heap
Heap operations: adjust, create, sort
Implement priority queue using heap
Basic concepts
Heaps are also called priority queue s
Logical Definition:
The n element sequences {k1,k2...ki...kn} are called heaps if and only if they satisfy the following relationships:
(ki <= k2i,ki <= k2i+1)perhaps(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)
The implementation of heap is a kind of binary tree by constructing binary heap.
Nature:
1. Any node is smaller or larger than all of its descendants, and the smallest or largest element is at the root of the heap (heap ordering).The heap with the largest root node is called the maximum heap or the large root heap, and the heap with the smallest root node is called the minimum heap or the small root heap.Common heaps are the Binary heap, the Fibonacci heap, and so on.
2. A heap is always a complete tree.The heap only needs to satisfy that the parent node is larger than two children, and there is no requirement between the children.As a full tree, the nodes in a layer are filled from left to right.If a node has no left son, it must have no right son.And if there are nodes in layer h, layer h-1 must be filled.
Heap Operation
Adjust heap
void adjust_max_heap_recursive(int *datas, int length, int i)//Recursive calls, maximum heap adjustment
{
int left,right,largest;
int temp;
left = LEFT(i);//left child
right = RIGHT(i);//right child
//find the largest value among left and right and i
if(left<=length && datas[left]>datas[i]) largest = left;
else largest = i;
if(right <= length && datas[right] >datas[largest]) largest = right;
//exchange i and largest
if(largest != i)
{
temp = datas[i];
datas[i] = datas[largest];
datas[largest] = temp;
//recursive call the function, adjust from largest
adjust_max_heap(datas, length, largest);
}
}
void adjust_max_heap(int *datas,int length,int i)//Non-recursive calls, maximum heap adjustment
{
int left,right,largest;
int temp;
while(1)
{
left = LEFT(i); //left child
right = RIGHT(i); //right child
//find the largest value among left and rihgt and i.
if(left <= length && datas[left] > datas[i])
largest = left;
else
largest = i;
if(right <= length && datas[right] > datas[largest])
largest = right;
//exchange i and largest
if(largest != i)
{
temp = datas[i];
datas[i] = datas[largest];
datas[largest] = temp;
i = largest;
continue;
}
else
break;
}
}
Create Heap
Idea: Add elements one by one and adjust to the maximum or minimum heap until all elements are processed.
void build_max_heap(int *datas,int length)//Create maximum heap
{
int i;
//build max heap from the last parent node
for(i=length/2;i>0;i—)//From the last non-leaf node (n/2) to the end of the first leaf (1)
adjust_max_heap(datas,length,i);
}
Heap Sorting
Idea: Create a heap and then adjust the heap from back to front.
void heap_sort(int *datas,int length)
{
int i,temp;
//bulid max heap
build_max_heap(datas,length);//Create maximum heap
i=length;
//exchange the first value to the last unitl i=1
while(i>1)
{
temp = datas[i];
datas[i] = datas[1];
datas[1] =temp;
i--;
//adjust max heap,make sure the fisrt value is the largest
adjust_max_heap(datas,i,1);
}
}Time complexity of heap sorting algorithm: adjusting heap processes to satisfy recursion T(n)<=T(2n/3)+θ(1)，Yes master Definition knows T(n) = O(lgn)，A loop is executed during the heap sorting process, calling the maximum heap tuning function with an overall time complexity ofO(nlgn).
Priority Queue
There are two types of priority queues: the maximum priority queue and the minimum priority queue, which can be implemented with the maximum heap and the minimum heap, respectively.
Priority Queue Operation (Maximum Priority Queue)--Maximum heap)
Insert: returns the largest (priority) element: returns the first element of the largest heap
Maximum (priority) elements are queued: delete the first element of the maximum heap, move the last to the first location, and adjust the heap from the first location.
Increase priority: Increase priority, and then adjust heap up from the parent node of the node.
Enqueue: Insert the end of the heap and adjust the heap up from the parent node of the node.
Priority Queue Application
Realization FIFOqueue: Incremental Priority
Realization FILOStack: Decreasing Priority
Reprinted at: https://www.cnblogs.com/lucas-hsueh/p/3732155.html