Preface:
Heap is a completely binary tree with the following properties
Each node is greater than or equal to its left and right child nodes, which is called the large top (root) heap.
Each node is less than or equal to its left and right child nodes, which is called a small top (root) heap
Complete binary tree subscripts conversion formula in array
Suppose the heap root node starts with 1 (it is convenient to calculate from 1, and the subscript of 0 is empty)
The following is a non-root node with the number i as an example, and the subscript formula for calculating its associated node is:
Its parent node: i/2
The left child: 2i
His right child: 2i+1
Note: Putting this completely binary tree into an array in layer order (no subscript 0 is used), then the above relationship expression is satisfied
Code workflow
Overall process
a. Create the initial heap from the lowest non-leaf node according to the node conversion formula, and then from right to left (bottom up) to root by creating the initial heap from the root in turn, from right to left (bottom up) to the root.
b. Loop n-1 times, execute it in turn: after conditional judgment, exchange the top and tail elements of the heap
Rebuild the element except the heap tail to the new heap, all the way to the root
Reconstruct heap function process
Receive parameter start subscript and array effective length
Save the heap top and build the heap from top to bottom. If the heap top (temporary heap top) is smaller than the child node (in the large heap), the child will assign the temporary heap top position (no swap function exchange is required, swap is not necessary), and let the temporary heap top position specify the child node
The for loop will definitely find the appropriate position. At this time, the position pointed to by the temporary heap top may be the position when the function is called, or it may change (a forced assignment is performed in the code)
Large and small top pile usage scenarios
Large top heap is used for ascending sorting, while small top heap is used for descending sorting
Time complexity
O(nlogn)
Unstable
Code
#include <>
#include <>
#define MAXSIZE 9
typedef struct {
int r[MAXSIZE+1]; // first index used as tmp, not real data
int len;
}SqList;
void swap(SqList *L, int i, int j) {
int tmp = L->r[i];
L->r[i] = L->r[j];
L->r[j] = tmp;
}
void heap_adjust(SqList *L, int s, int len) {
int temp, i;
temp = L->r[s]; // s(start) index may be a invalid element in this heap and try adjust
for (i=s*2; i<=len; i*=2) { // compare with child
if (i<len && L->r[i] < L->r[i+1]) {
i++; // select the max child
}
if (temp >= L->r[i]) {
break; // need not adjust
}
L->r[s] = L->r[i]; //need not swap, because always use temp compare with next level child
s = i; // next loop, now s sub tree root node may be a invalid element
}
L->r[s] = temp; // finally, must be found the right place(or not changed)
}
void heap_adjust_2(SqList *L, int s, int len) {
printf("use test function\n");
int temp, i;
temp = L->r[s]; // s(start) index may be a invalid element in this heap and try adjust
for (i=s*2; i<=len; i*=2) { // compare with child
if (i<len && L->r[i] < L->r[i+1]) {
i++; // select the max child
}
if (temp >= L->r[i]) {
break; // need not adjust
}
swap(L, s, i); //need not swap, because always use temp compare with next level child
s = i; // next loop, now s sub tree root node may be a invalid element
}
L->r[s] = temp; // finally, must be found the right place(or not changed)
}
void heap_sort(SqList *L) {
// init serial to a heap first(type: big top), down->up and right->left
int i, j;
for (i=L->len/2; i>0; --i) {
heap_adjust(L, i, L->len);
//heap_adjust_2(L, i, L->len);
}
for (j=L->len; j>1; --j) {
swap(L, 1, j);
heap_adjust(L, 1, j-1);
}
}
int main(void) {
SqList list = {
{999,50,10,90,30,70,40,80,60,20},
MAXSIZE
};
heap_sort(&list);
printf("after heap_sort:\n");
for (int i=0; i<=MAXSIZE; i++) {
printf("index: %d, value: %d\n",i,[i]);
}
return 0;
}
output
➜ c gcc sort_heap.c && ./
after heap_sort:
index: 0, value: 999
index: 1, value: 10
index: 2, value: 20
index: 3, value: 30
index: 4, value: 40
index: 5, value: 50
index: 6, value: 60
index: 7, value: 70
index: 8, value: 80
index: 9, value: 90
This is the end of this article about C language sorting. For more related C language sorting, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!