# Introduction to Algorithms Chapter VI Heap Sorting

Basic concepts of heap, maximum heap, minimum heap

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

{

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

}

}

{
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)
}

### 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;
datas =temp;
i--;
//adjust max heap,make sure the fisrt value is the largest
}
}

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

Added by weneedmoregold on Thu, 08 Aug 2019 19:47:58 +0300