Shulou(Shulou.com)05/31 Report--

Today, the editor will share with you the relevant knowledge points of the sample analysis of C language data structure heap sorting. The content is detailed and the logic is clear. I believe most people still know too much about this knowledge, so share this article for your reference. I hope you can get something after reading this article, let's take a look at it.

TOP. Preface to heap sort

What is heap sorting? If you were given the following code to improve heap sorting, how would you write it? What would you do?

Void HeapSort (int* a, int n) {} int main () {int arr [] = {4, 2, 7, 8, 5, 1, 0, 0, 6}; int sz = sizeof (arr) / sizoef (arr [0]); HeapSort (arr, sz); return 0;}

Heap sorting is to sort a set of data by using the data structure of heap.

Therefore, the heap sorting as a whole is completed in two steps.

The first step is to build a pile

Step two, sort.

Note: the following code is for ascending order of a set of data

First, adjust the heap sort down

Yes, the downward adjustment method is the best heap sort.

I don't really want to introduce the kind of heap sort that adjusts hip pulling up, but we often use this excellent downward sort.

The difference between the two lies in the method of building the heap. One is to build a down stack O (N), and the other is to build an upward pile O (N*logN).

The concrete proof uses the simple sequence formula of high school.

1. Adjust the skills of building heaps downward

There are also two cases of building a pile down.

1. Build a large pile

two。 Build a small pile

So in the end, build a big pile or a small pile?

Explanation: building a heap depends on whether you want to sort ascending or descending. If you build a large heap, because the number at the top of the heap is the largest, when we sort the heap down, we need to swap the largest to the bottom of the heap every time. So the order that leads to the final heap is ascending.

Before building a big pile

After building a large pile

After adjusting the sort down

At this point, the array is ordered.

Conclusion: the essence is to build a heap on an array. Build a large pile in ascending order and a small pile in descending order.

Heap building idea code

Train of thought:

Because the leaf node itself is a large pile, the heap is built downwards from the father node of the last leaf node.

This ensures that every pile built is a large pile.

Note:

1. Pay attention to the loop end condition and the boundary problem child + 1 in the if statement

< n 2.注意完全二叉树父子关系公式 #include //交换void swap(int* x, int* y){ int t = 0; t = *x; *x = *y; *y = t;}//向下调整void AdjustDown(int* a, int n, int root){ int parent = root; int child = parent * 2 + 1; while (child < n) { //每次调整都需要从左右两边选出孩子最大的那个 //假设坐孩子较大，选出左右孩子大的那个 if (child + 1 < n && a[child + 1] >

A [child]) {+ + child;} / / start the adjustment. If (a [child] > a [parent]) {swap (& a [child], & a [parent]); parent = child; child = parent * 2 + 1; if not satisfied, jump out and start the next for cycle adjustment. Else {break;}} void HeapSort (int* a, int n) {/ / downward adjust build int I = 0; for (I = (n-1-1) / 2; I > = 0; iMel -) {AdjustDown (a, n, I) }} int main () {int arr [] = {4, 2, 7, 7, 5, 5, 5, 1, 0, 0, 6, 6; int sz = sizeof (arr) / sizeof (arr [0]); HeapSort (arr, sz); return 0;} 2. Adjust the order downward and adjust the train of thought

1. Exchange the data with the top of the stack from the bottom of the stack.

two。 Adjust down the value of the exchanged heap top. When adjusting downwards, ignore the maximum value swapped to the bottom of the stack.

3. Continue to cycle through steps 1 and 2 until the end of the second positive number.

Sort the whole code void swap (int* x, int* y) {int t = 0; t = * x; * x = * y; * y = t;} void AdjustDown (int* a, int n, int root) {int parent = root; int child = parent * 2 + 1; while (child

< n) { //每次调整都需要从左右两边选出孩子最大的那个 //假设坐孩子较大，选出左右孩子大的那个 if (child + 1 < n && a[child + 1] >

A [child]) {+ + child;} / / start the adjustment. If (a [child] > a [parent]) {swap (& a [child], & a [parent]); parent = child; child = parent * 2 + 1; if not satisfied, jump out and start the next for cycle adjustment. Else {break;}} void HeapSort (int* a, int n) {/ / downward adjust build int I = 0; for (I = (n-1-1) / 2; I > = 0; iMel -) {AdjustDown (a, n, I) } / / downwards adjust the sort int end = 0; for (end = nmur1; end > 0; end--) {swap (& a [0], & a [end]); / / ignore the maximum value when adjusting downwards, so end is NMur1. AdjustDown (a, end, 0);} int main () {int arr [] = {4, sz 2, return 7, 8, 5, 1, 0, 6}; int sz = sizeof (arr) / sizeof (arr [0]); HeapSort (arr, sz); return 0;} 3. Time complexity (difficulty) downwards adjust int I = 0; for (I = (n-1-1) / 2; I > = 0; iMel -) {AdjustDown (a, n, I);}

The misunderstanding of many people is that their time complexity is N*Log2N. This is wrong.

The calculation of time complexity is based on ideas, not circular guesses.

When the binary tree is full, in the worst case, all the upper layers need to be adjusted downwards except the last one.

Number of adjustments in the worst case = number of data per layer * number of downward adjustments

The number of downward adjustment of the first layer is hmur1, and the number of nodes is 21-1.

The number of downward adjustments in the second layer is hmur2, and the number of nodes is 22-1.

The downward adjustment number of layer h-1 is 1, and the number of nodes is 2h-1-1.

So the total number of adjustments is nRV n = 20 * (hmur1) + 21 * (hmer2) + … + 2h-1-1 * (1)

According to the dislocation subtraction of high school, we get n = 1 − hourly 21 ~ 22 +. + 2 hours − 2 hours − 1

N = 2h − h − 1 is obtained from the sum of the first n terms of the proportional sequence.

From the properties of binary tree Nissan 2h − 1 and h = log2 (Numb1), we get nasty N − log2 (Numb1).

The asymptotic representation of large O is n = O (N).

Adjust downward (N*LogN)

Need to adjust nMel downwards once. The height that needs to be adjusted each time is the number of LogN,N nodes, because the number of nodes is one less at a time.

So the total number of times adjusted by nMel 1 time = log2+log3+... + log (n Mel 1) + log (n) ≈ log (n!)

Log (n!) is obtained from mathematical knowledge. Is a function of the same order as nlog (n).

So adjust the sorting time complexity down to N*LogN

So the complexity of heap sorting time is N + N*LogN.

The asymptotic representation of large O is O (N*LogN).

Summary: heap sort time complexity O (N*LogN)

Second, adjust the heap sort up

The only difference between upward and downward sorting is the difference in heap building, resulting in a slight difference in heap-building time complexity.

1. Adjust the construction of pile up

Adjust the heap building time complexity up to N*LogN. The specific reason still needs to go through cruel mathematical calculation. Kids don't. But after consulting the data on the Internet, I found the method of calculation again. As shown in the picture.

According to the properties of binary tree: h = Log2 (Numb1)

You can replace T (h) = 2h * (hmur2) + 2 with:

So generally speaking, the upward adjustment of the heap building time complexity is O (N * LogN).

two。 Heap code

Idea: start with the second element, focus only on the first two elements to build the heap, and then add the elements to build the heap so that it is always a heap.

Although the time complexity of adjusting the heap up is a little higher, the code is a little easier than the downward adjustment.

Void AdjustUp (int* a, int child) {/ / represents the parent node first. Int parent = (child-1) / 2; while (child > 0) {/ / compare the child with the father and begin to adjust upward. If (a [child] > a [parent]) {swap (& a [child], & a [parent]); child = parent; parent = (child-1) / 2;} else {break The above is all the contents of the article "sample Analysis of heap sorting of C language data structures". Thank you for reading! I believe you will gain a lot after reading this article. The editor will update different knowledge for you every day. If you want to learn more knowledge, please pay attention to the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.