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

In this article, the editor introduces in detail "how C language realizes the structure and interface of heap and heap". The content is detailed, the steps are clear, and the details are handled properly. I hope this article "how to realize the structure and interface of heap and heap in C language" can help you solve your doubts. Let's follow the editor's ideas to learn new knowledge.

I. structure and implementation of heap (important) 1.1 Sequential structure of binary tree

Ordinary binary trees are not suitable to be stored in arrays because there may be a lot of space waste. On the other hand, complete binary tree is more suitable for sequential structure storage. In reality, we usually use an array of sequential structures to store the heap (a complete binary tree). It should be noted that the heap here is different from the heap in the virtual process address space of the operating system, one is the data structure, and the other is the segmentation of an area of administrative memory in the operating system.

1.2 concept and structure of heap

Heap is a general term for a special kind of data structure in computer science. A heap is usually an array object that can be thought of as a complete binary tree. The heap always meets the following properties:

The value of a node in the heap is always not greater than or less than the value of its parent node

The heap is always a complete binary tree.

Heap is a nonlinear data structure, which is equivalent to an one-dimensional array and has two direct successors.

[big Root pile and small Root pile]:

The heap with the largest root node is called the big root heap, and all fathers in the tree are greater than or equal to their children.

The smallest heap at the root node is called the small root heap, and all fathers in the tree are less than or equal to their children.

[thinking] what are the characteristics of this big root pile and small root pile?

According to this feature, we can do a lot of things, such as TopK problem (find the first K maximum / minimum number in a pile of data), and there are many examples in life, such as thousands of stores in the ordering software. I want to select the ten Sichuan restaurants with the most favorable comments in the region. We don't have to sort all the data, we just need to take out the first K maximum / minimum data. It is also more efficient to use heap sorting.

1.3 implementation of heap 1.3.1 Down adjustment algorithm for heap

Here is an array that is logically regarded as a complete binary tree. We can adjust it into a small heap by adjusting it down from the root node. The downward adjustment algorithm has a premise: the left and right subtrees of the node must be a (large / small) heap before they can be adjusted.

Int array [] = {27,15,19,18,28,34, 65,45,25,37}; / / the left and right subtrees of the root node are all small heaps.

In the above array, because the left and right subtrees of the root node are small heaps, we start with the root node and adjust it into a small heap.

Adjust the algorithm idea down (into a small heap):

Starting from the root node, it keeps going downwards.

Select the "youngest child" of the left and right children of the root node and compare it with the "father".

If the father is smaller than the child, there is no need to deal with it, the whole tree is already a small pile.

If the father is larger than the child, change places with the father, and continue to adjust the position of the original young child as the father until it reaches the leaf node.

Downward adjustment algorithm process demonstration (adjust into a small heap, adjust the large nodes down):

Adjust the algorithm code down:

/ / adjust the algorithm downward, build a small heap, and adjust the large nodes downwards. / / the premise is: the left and right subtrees are all small heaps of void AdjustDown (int* a, int size, int parent) {/ / pointing to the left child. By default, the minimum left child int child = parent * 2 + 1; while (child)

< size) { // 1. 选出左右孩子最小的那个，先判断右孩子是否存在 if (child + 1 < size && a[child] >

A [child+ 1]) {child++; / / point to the right child} / / 2. The youngest child compares if (a [parent] > a [child]) / / if the father is greater than the child {/ / the father and the child exchange positions Swap (& a [parent], & a [child]) / / update the father-son subscript, and the original youngest child as the father continues to downgrade parent = child; child = parent * 2 + 1 } else / / if the father is smaller than the child, it is already a small heap, stop adjusting {break;}} 1.3.2 downward adjust the time complexity of the algorithm

We use the full binary tree to calculate, in the worst case, the downward adjustment algorithm compares the height of the full binary tree at most once, then it shows that the downward adjustment algorithm can reduce the height of the full binary tree at most once, and the height of the full binary tree with n nodes is log2 (n = 1), so the estimated time complexity is O (log2n).

1.3.3 creation of heap (downward adjustment)

Here is an array that can logically be thought of as a complete binary tree, but not a heap, and we need to build it into a heap by algorithm. If the left and right subtree of the root node is not a (large / small) heap, how should we adjust it?

We adjust backwards, from bottom to top, starting from "the subtree of the penultimate non-leaf node", traversing all the non-leaf nodes in turn, and "adjusting down" each subtree into a (large / small) heap all the way to the "root node". You can build a (large / small) heap.

Why adjust backwards? In this way, we can regard the left and right subtree of the penultimate non-leaf node subtree as a (large / small) heap, and then we can use the downward adjustment algorithm. For example, the yellow-filled subtree in the image below, the left subtree 6 of 3 can be seen as a large pile.

[example]: group the following numbers into a large heap

Int a [] = {1, 5, 3, 8, 7, 6}

Demonstration of the heap building process (take building a large heap as an example): traverse all the non-leaf nodes from bottom to top, and adjust each subtree down separately.

In each step, the trees in the box are adjusted down to a large heap.

Heap code:

/ / Exchange function void Swap (int* a, int* b) {int tmp = * a; * a = * b; * b = tmp } / / adjust the algorithm downward, build a large heap, and adjust the small nodes downwards / / on the premise that both the left and right subtrees are large piles of void AdjustDown (int* a, int size, int parent) {/ / pointing to the left child. By default, the maximum int child of the left child is int child = parent * 2 + 1; while (child

< size) { // 1. 选出左右孩子最大的那个，先判断右孩子是否存在 if (child + 1 < size && a[child] < a[child + 1]) { child++; // 指向右孩子 } // 2. 最大的孩子与父亲比较 if (a[parent] < a[child]) // 如果父亲小于孩子 { // 父亲与孩子交换位置 Swap(&a[parent], &a[child]); // 更新父子下标，原先最大的孩子作为父亲，继续往下调 parent = child; child = parent * 2 + 1; } else // 如果父亲大于孩子，说明已经为大堆了，停止调整 { break; } }}void HeapSort(int* a, int size){ /* 建堆（大堆） * 倒着调整，从倒数第一个非叶子节点的子树进行向下调整，直到调整到根节点的树 */ int parent = ((size - 1) - 1) / 2; // 最后一个叶子节点的父亲的下标 for (int i = parent; i >

= 0; iMurt -) / / traverse all the subtrees from bottom to top, and adjust them {AdjustDown (a, size, I) } / * heap sort * sort ascending order-- > build a large heap, select the largest number each time and put it in the last * descending order-> build a small heap, and select the smallest number each time to put it in the last * / the following is the ascending order: int end = size-1 / / record the subscript while (end > 0) {Swap (& a [0], & a [end]) of the last element in the heap; / / swap the heap top element with the last element in the heap, putting the maximum number (heap top) to the last AdjustDown (a, end, 0). / / without looking at the last number, starting from the root node, adjust the previous number down into a large pile of end--;} 1.3.4 heap sort

Sort ascending order-> build a big pile:

[thinking] is it all right to arrange the ascending order and build a small pile? Yes, it is, but it's not interesting.

First of all, build a small heap for n numbers, select the smallest number, then build a small heap for the remaining one, select the second smallest number, and repeat the above process over and over again. The heap time complexity of building n numbers is O (N), so the above operation time complexity is O (N2), the efficiency is too low, especially when the amount of data is large, the efficiency is lower, and the value of the heap is not reflected, it is better to use direct sorting.

[best method] sort in ascending order, because the numbers are getting bigger and bigger, you need to find the largest numbers, and you have to build a lot of them.

First of all, build a big pile of n.

Swap the largest number (top of the heap) with the last number, and put the maximum number last.

The heap structure of the previous nmur1 has not been destroyed (the last number does not look inside the heap), and the left and right subtrees of the root node are still a large heap, so we can select the second largest number by adjusting it down into a large heap, put it in the penultimate position, and then repeat the above steps.

[time complexity]: the complexity of heap building time is O (N), and the time complexity of downward adjustment is O (log2N). Here, we adjust Nmuri downward at most 2 times, so the complexity of heap sorting time is O (N*log2N), which is very efficient.

Sort and descend-- > build a small pile:

[best method] sort the descending order, because the number is getting smaller and smaller, you need to find the smallest number, and you have to build a small pile.

First of all, build a small heap of n.

Swap the smallest number (top of the heap) with the last number, and put the smallest number at the end.

The heap structure of the previous nmur1 has not been destroyed (the last number does not look inside the heap), and the left and right subtrees of the root node are still small heaps, so we can select the second smallest number by adjusting it down into a small heap, put it in the penultimate position, and then repeat the above steps.

[time complexity]: the complexity of heap building time is O (N), and the time complexity of downward adjustment is O (log2N). Here, we adjust Nmuri downward at most 2 times, so the complexity of heap sorting time is O (N*log2N), which is very efficient.

1.3.5 time complexity of building a heap

Because the heap is a complete binary tree, and the full binary tree is also a complete binary tree, in order to simplify the use of full binary tree to prove, it is easier to calculate (the time complexity originally looks like an approximate value, and a few more nodes will not affect the final result):

The heap should be adjusted from the penultimate non-leaf node, that is, from the penultimate layer, and the time complexity formula can be obtained:

T (n) = ∑ (number of nodes per layer ∗ (heap height − current number of layers)

Therefore, the time complexity of building a heap is O (N).

[after so much has been learned above, here is a little summary]

The downward adjustment algorithm of the heap is to adjust the tree rooted at the node into a small / large heap on the premise that both the left and right subtrees of the node are a small / large heap.

The creation of the heap is adjusted backwards, from bottom to top, starting from the subtree of the penultimate non-leaf node, traversing all the subtrees in turn and adjusting them down respectively.

Time complexity: the downward adjustment algorithm of the heap is O (log2N) and the creation of the heap is O (N).

2. Implementation of related interfaces of heap (take large heap as an example)

First create a new project (the blogger uses VS2019)

Heap.h (heap type definition, interface function declaration, referenced header file)

Heap.c (implementation of heap interface function)

Test.c (main function, each interface function of the test reactor)

The Heap.h header file code is as follows:

# pragma once#include / / printf, perror#include / / bool#include / / assert#include / / malloc, free#include / / memcpytypedef int HPDataType;typedef struct Heap {HPDataType* a; / / point to the number of effective elements in the dynamically opened array int capacity; / / d capacity} Heap;// exchange function void Swap (HPDataType* a, HPDataType* b) / / Down adjustment function (HPDataType* a, int size, int parent); / / up adjustment function (set to big heap, big up) void AdjustUp (HPDataType* a, int child); / initialize heap void HeapInit (Heap* php, HPDataType* arr, int n); / / destroy heap void HeapDestroy (Heap* php) / / insert the element (insert to the end of the heap), insert it and keep it as heap void HeapPush (Heap* php, int x); / / delete the heap top element, and keep it still heap void HeapPop (Heap* php) after deletion; / / get the heap top element, that is, the maximum value HPDataType HeapTop (Heap* php); / / determine whether the heap is empty, return true if it is empty, and falsebool HeapEmpty (Heap* php) if it is not empty / / get the number of valid elements in the heap int HeapSize (Heap* php); / / print the heap void HeapPrint (Heap* php); 2.1initialization of the heap

To initialize the heap, you first need to implement a downward adjustment algorithm:

/ / Exchange function void Swap (HPDataType* a, HPDataType* b) {HPDataType tmp; tmp = * a; * a = * b; * b = tmp;} / / downward adjustment algorithm (adjust the small ones down) void AdjustDown (HPDataType* a, int size, int parent) {/ / left child subscript, initial default left child maximum int child = parent * 2 + 1 While (child

< size) { // 选出左右孩子最大的那个，先判断右孩子是否存在 if (child + 1 < size && a[child] < a[child + 1]) { child++; // 右孩子最大 } // 最大的孩子与父亲比较 if (a[parent] < a[child]) // 如果父亲小于孩子 { // 父亲与孩子交换位置 Swap(&a[parent], &a[child]); // 更新父子下标，原先最大的孩子作为父亲，继续往下调 parent = child; child = parent * 2 + 1; } else // 如果父亲大于孩子，说明已经为大堆了，停止调整 { break; } }} 堆的初始化代码： // 初始化堆，用一个给定的数组来初始化void HeapInit(Heap* php, HPDataType* arr, int n){ assert(php); // 断言 // 动态开辟n个空间 php->

A = (HPDataType*) malloc (sizeof (HPDataType) * n); if (php- > a = = NULL) {perror ("malloc"); exit (- 1);} / / copy the element values of a given array to memcpy (php- > a, arr, sizeof (HPDataType) * n); php- > size = php- > capacity = n / / build the heap (Jian Dadui) int parent = ((php- > size-1)-1) / 2; / / the penultimate non-leaf node subscript for (int I = parent; I > = 0; iMel -) / / traverse all the subtrees from bottom to top, and adjust them {AdjustDown (php- > a, php- > size, I) Void HeapDestroy (Heap* php) {assert (php); free (php- > a); / / release dynamically opened space php- > a = NULL; php- > size = php- > capacity = 0;} 2.3 insertion of heap

First insert a new element into the end of the array, starting with the new element inserted, and adjust the algorithm up until the (large / small) heap is satisfied.

The process of inserting the heap demonstrates:

To insert the heap, you first need to implement an upward adjustment algorithm:

/ / upward adjustment algorithm (adjust the big ones up) void AdjustUp (HPDataType* a, int child) {/ / the subscript of the parent node int parent = (child-1) / 2 / / while (parent > = 0) parent will not be less than 0 while (child > 0) {/ / compare the child with the father if (a [child] > a [parent]) / / if the child is larger than the father {/ / exchange with the father Swap (& a [child] & a [parent]) / / update the father-son subscript. The father, as a child, continues to upgrade child = parent; parent = (child-1) / 2. } else / / if the child is smaller than the father, it is already a big pile, stop adjusting {break;}}

Insert code for the heap:

/ / insert the element (insert to the end of the heap), insert it and keep it as heap void HeapPush (Heap* php, int x) {assert (php); / / first check whether the space is full if (php- > capacity = = php- > size) {/ / double php- > capacity * = 2 HPDataType* tmp = (HPDataType*) realloc (php- > a, sizeof (HPDataType) * php- > capacity); if (tmp! = NULL) {php- > a = tmp; tmp = NULL;}} / / insert element php- > a [php-> size] = x Php- > size++; / / starting with the inserted element, adjust upward to keep it still heap AdjustUp (php- > a, php- > heap-1);} 2.4 deletion of heap

Swap the top element of the heap with the last element (this becomes tail deletion, which is convenient)

Delete the last element in the heap

Starting from the root node, adjust the remaining elements down to a (large / small) heap

The process of deleting a heap demonstrates:

To insert the heap, you first need to implement a downward adjustment algorithm: it has already been implemented before, so it will not be shown here.

Delete code for the heap:

/ / remove the heap top element and leave it as heap void HeapPop (Heap* php) {assert (php); assert (! HeapEmpty (php)); / / the heap cannot be empty / / swap the heap top element with the last element Swap (& php- > a [0], & php- > a [php-> size-1])) / / delete the last element in the heap php- > size--; / / starting from the root node, adjust the remaining elements down into a large heap, leaving it still heap AdjustDown (php- > a, php- > size, 0);} 2.5 get the heap top element / / get the heap top element, that is, the maximum value HPDataType HeapTop (Heap* php) {assert (php) Assert (! HeapEmpty (php)); / / heap cannot be empty return php- > a [0]; determine whether the heap is empty / / determine whether the heap is empty, return true if it is empty, return falsebool HeapEmpty (Heap* php) {assert (php) if not empty; return php- > size = = 0;} 2.7. find the first k largest elements in the heap

The relevant interface of the heap has been implemented, because it is a large heap, so we can easily find the first k largest elements in the heap.

This should be distinguished from the previous heap sort, where we do not sort all the elements in the heap.

Void TestHeap () {int a [] = {1 hp, a, sizeof (a) / sizeof (a [0]); / / initialize heap int k = 0; scanf ("% d", & k); printf ("find the first% d largest elements in the heap:\ n", k) While (! HeapEmpty (& hp) & & KMurray -) {printf ("% d", HeapTop (& hp)); / / get heap top element HeapPop (& hp); / / delete heap top element} printf ("\ n");}

Running result:

2.8 creation of heap (upward adjustment)

Here is an array that logically can be thought of as a complete binary tree, but not a heap, which we need to build into a heap through the "upward adjustment algorithm". If the left and right subtree of the root node is not a (large / small) heap, how should we adjust it?

From top to bottom, we start with the "left child of the first node (that is, the root node)", traverse all the nodes in turn, and "adjust" each node up to the "last node". You can build a (large / small) heap.

We think of the "first element" in the array as a "heap", and the remaining elements are inserted into the "heap" in turn. Earlier, we also implemented the plug-in interface of the heap, which is adjusted upwards.

/ / upward tuning algorithm heap void CreateHeap (int* a, int size) {/ / regards the first element as a heap, and then inserts the remaining elements into the heap for (int I = 1; I < size; iTunes +) {AdjustUp (a, I) }} here, the article "how to implement heap and its structure and interface in C language" has been introduced. If you want to master the knowledge points of this article, you still need to practice and use it before you can understand it. If you want to know more about related articles, 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.