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

This article mainly introduces the relevant knowledge of how to realize the C language heap and what the heap sorting is, the content is detailed and easy to understand, the operation is simple and fast, and has a certain reference value. I believe you will gain something after reading this article on how to realize the C language heap and what heap sorting is. Let's take a look at it.

I. the key points of this chapter

Introduction of heap

Interface implementation of heap

Heap sort

II. Introduction of reactor 2.1

Generally speaking, the heap is a continuous array structure in physical structure and a complete binary tree in logical structure.

But to be satisfied

The value of each parent node must be greater than that of the child node, and such a heap is called a large heap.

The value of each parent node must be less than that of the child node, and such a heap is called a small heap.

So here is a small pile.

Baidu encyclopedia:

The definition of heap is as follows: the sequence of n elements {K1 ~ K2 ~ Ki, … , kn} is called a heap if and only if the lower relation is satisfied.

If the one-dimensional array corresponding to this sequence (that is, using the one-dimensional array as the storage structure of the sequence) is regarded as a complete binary tree, the meaning of the heap shows that the values of all non-terminal nodes in the complete binary tree are not greater than (or not less than) the values of their left and right child nodes. As a result, if the sequence {K1J K2, … , kn} is a heap, the top element of the heap (or the root of a complete binary tree) must be the minimum (or maximum) value of n elements in the sequence.

The following sequence is stacked ().

A.97pr 56pr 38rec 66je 23je 42jue 12 / / not a big heap nor a small heap, that is, not a heap.

B.23pr 86pr 48rec 3e 35pr 39pr 42 / / neither a big heap nor a small heap, that is, not a heap.

C.05pr 56je 20jr 23jr 40je 38je 29 / / neither a big heap nor a small heap, that is, not a heap.

D.05, 23, 16, 68, 94, 72, 71, 73 / is a small pile.

Only D is a heap and a small heap, so the answer is D.

The logical structure of D:

The array subscript of the parent node and the child node has the following relationship:

Left_child= (parent+1) * 2

Right_child= (parent+2) * 2

Parent= (child-1) / 2 (child applies to both left and right children here)

There is no need to prove the above, but we can verify that taking the logical structure of figure D above as an example, the parent subscript of 16 is 2, the subscript of 72 is 5, and the subscript of 5, 71 is 6, which satisfies left_child= (parent+1) * 2, right_child= (parent+2) * 2, and parent= (child-1) / 2.

Order must be heap, heap is not necessarily orderly.

At the same time, the array at the top of the stack is the largest number of the whole array or the smallest number of the whole array.

Interface implementation of 2.2 heap

The first thing we want to do is to create a heap, which is actually an array, in this case a dynamic array.

Typedef int HPDataType;typedef struct Heap {HPDataType* a; size_t size; size_t capacity;} HP

After the heap is created, we need to initialize it.

First interface:

Void HeapInit (HP* php)

Know how to set an in the heap to NULL,size and capacity to 0.

Or here you can set an initial value where capacity is not zero.

Reference Code:

Void HeapInit (HP* php) {assert (php); php- > a = NULL; php- > size = php- > capacity = 0;}

After we initialize the heap, we also destroy the heap at the end.

Second interface:

Void HeapDestroy (HP* php)

Destroy the heap, that is, destroy a dynamic array

Reference Code:

Void HeapDestroy (HP* php) {assert (php); free (php- > a); php- > a = NULL; php- > size = php- > capacity = 0;}

Now we can consider inserting data into the heap, requiring the heap after the new element is inserted.

The third interface:

Void HeapPush (HP* php, HPDataType x)

The heap does not require a new element to be inserted in any place, you can insert a new element anywhere, but make sure that the new element is still the heap after the new element is inserted.

Because the insertion complexity of the array in the header or in the middle is O (N), and it is not necessarily a heap after insertion.

So we consider inserting a new element directly at the end of the array and then using a function to adjust the order of the array so that it is still a heap.

Then the core code is this adjustment algorithm.

Let's take a look at this heap and how to adjust it after inserting a new element.

We insert 22 at the end of the array, where the original heap is a small heap, and we need to adjust each parent node from the bottom up so that the heap is still a small heap.

In other words: we just need to adjust the order of the colored nodes below.

Exchange process: if the child node is smaller than the parent node, swap them and then iterate.

If the child node is larger than the father node, jump out of the loop.

Iterative process: assign the subscript of the parent node to the subscript of the child node, and then recalculate the subscript of the parent node, calculated by parent= (child-1) / 2.

Reference Code:

Void AdjustUp (HPDataType* a, size_t child) {size_t parent = (child-1) / 2; while (child > 0) {/ / if the child is smaller than the father, exchange if (a [child]

< a[parent]) { Swap(&a[child], &a[parent]); child = parent; parent = (child - 1) / 2; } //孩子大于父亲，则结束调整 else { break; } }}void HeapPush(HP* php, HPDataType x){ assert(php); //动态数组，空间不够要扩容 if (php->

Size = = php- > capacity) {size_t newCapacity = php- > capacity = 0.4: php- > capacity * 2; HPDataType* tmp = realloc (php- > a, sizeof (HPDataType) * newCapacity); if (tmp = = NULL) {printf ("realloc failed\ n"); exit (- 1) } php- > a = tmp; php- > capacity = newCapacity;} / / insert data php- > a [php-> size] = x; + + php- > size; / / adjust upwards to keep a small heap of AdjustUp (php- > a, php- > size-1);}

The above is the insertion of multiple data, so if you insert the first data, can this function still help us insert the data into the heap?

The answer is yes.

Now that you have Push data to the heap, it's natural to remove elements from the heap.

The deletion here is different from the deletion of the stack and queue, which means that the data at the top of the heap is deleted, and the heap is still a heap after deletion. Why only delete the data at the top of the heap? because it is simple and practical, this interface is ready for later heap sorting.

The fourth interface:

Void HeapPop (HP* php)

The idea is simple: delete the first element of the array and keep it a small heap.

How do I delete the first data?

The consideration here is to swap the first element of the array with the last element of the array, and delete the last element at the end of the exchange to achieve the effect of deleting the first element with a complexity of O (N). It can be mentioned here that this header deletion changes the relative order of the array elements.

After deletion, we have to make adjustments to make the heap still small.

So how to adjust it?

Here is a small pile

After the head is deleted

How to adjust it so that it is still a small pile?

The idea here is: adjust the algorithm downward, first parent=73, then select the smallest value of its child node, and then exchange between them. After the exchange, the child node is regarded as the new parent node, and continue to adjust downward until the left child of the father node does not exist.

Reference Code:

Void AdjustDown (HPDataType* a, size_t size, size_t root) {size_t parent = root; size_t child = parent * 2 + 1; while (child

< size) { // 1、选出左右孩子中小的那个 if (child + 1 < size && a[child+1] < a[child]) { ++child; } // 2、如果孩子小于父亲，则交换，并继续往下调整 if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } }} 这里需要注意的是，为什么循环的结束条件不是右孩子不存在呢？ 因为右孩子不存在时，也可能要进行交换。 比如： 还需要注意的是左孩子存在右孩子不一定存在 if (a[child+1] >

A [child]) {+ + child;}

Writing a [child+1] like this may cross the line, so add child+1

< size，保证child + 1 size >

0); / / swap the first element of the array with the last element and then delete the last element to achieve the purpose of header deletion. Swap (& php- > a [0], & php- > a [php-> size-1]);-- php- > size; / / downward adjustment algorithm AdjustDown (php- > a, php- > size, 0);}

Other APIs add:

Because it is relatively simple and easy to understand, it is given directly here.

Reference Code:

Bool HeapEmpty (HP* php) / / determines whether the heap is empty {assert (php); return php- > size = = 0;} size_t HeapSize (HP* php) / / the number of elements in the heap {assert (php); return php- > size;} HPDataType HeapTop (HP* php) / / takes the heap top data {assert (php); assert (php- > size > 0); return php- > a [0];} III.

Heap sorting: the purpose of sorting can be achieved by making use of the fact that the heap top node is the maximum or minimum value of the whole array.

For example, we have to arrange 1, 5, 2, 4, 8, 6, 10 in ascending order.

You can put these elements into the heap in turn, making the data a small heap.

Then we can take the first element of the heap, which is the smallest element in the whole array, in ascending order, so we need to put it in the first place, and then delete the top element of the heap. Since the purpose of our delete interface is to delete the top element of the heap and keep the heap still small, then after we call the delete interface, we take the element of the top of the heap, put it in the second position, and continue in turn. We can sort the data in ascending order.

Reference Code:

Void HeapSort (int* a, int size) {HP hp; HeapInit (& hp); / / build small heap for (int I = 0; I < size; + + I) {HeapPush (& hp, a [I]);} / / continuously sort the top elements of the heap size_t j = 0 While (! HeapEmpty (& hp)) {a [j] = HeapTop (& hp); jacks; HeapPop (& hp);} / / destroy the heap to prevent memory leaks HeapDestroy (& hp);}

The space complexity of heap sorting here is O (N), because a heap space of N elements is opened up in the heap area.

Heap sorting looks complicated, so what is its time complexity?

Build a small pile: 0 (N)

What HeapPop () executes at one time is: delete the top element of the heap (O (1)), and then compare it down in turn, the number of comparisons is high, because it is a complete binary tree, the time complexity of the comparison is O (logN).

Therefore, the time complexity of executing a HeapPop is O (logN).

Then continuously sort the elements on the top of the heap, take N elements, call HeapPop () N times, and the time complexity is O (N*logN).

The total time complexity is O (N) + O (N*logN). When N is very large, the added O (N) can be ignored.

The actual time complexity is: O (N*logN)

Space complexity: O (N)

Then the time complexity of heap sorting is O (N*logN).

Compared to O (bubble N) sorted by bubbles.

Heap sorting is obviously more efficient.

If N equals 1 million, bubbling will be executed 1 trillion times, while heap sorting will be executed 20 million times, so the efficiency can be imagined!

This is the end of the article on "how to implement the C language heap and what is the heap sorting". Thank you for reading! I believe that everyone has a certain understanding of the knowledge of "how to realize the C language heap and what the heap sorting is". If you want to learn more knowledge, you are welcome to follow 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.