Shulou(Shulou.com)06/02 Report--

This article is about how C language solves the binary heap problem. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

I. the concept of heap 1. Overview

Heap is a general term for a special kind of data structure in computer science. There are many implementations, such as: big top pile, small top pile, Fibonacci pile, left side pile, oblique pile and so on. From the number of sub-nodes, it can be divided into binary heap, N-fork heap and so on. This article will introduce the binary heap.

2. Definition

The binary heap is essentially a complete binary tree, so every insertion and deletion of elements can guarantee O (log2n) O (log_2n) O (log2n). According to the partial order rules of the heap, it is divided into small top heap and large top heap. Small top heap, as the name implies, the root node has the smallest keyword; large top heap is the opposite. As shown in the figure, it represents a large top heap.

3. Nature

In the case of a large top pile, for example, it always satisfies the following properties:

1) the empty tree is a large top heap

2) the keyword of a node in the big top heap is less than or equal to the keyword of its parent node

3) the big top pile is a complete binary tree. For more information about complete binary trees, please refer to: drawing complete binary trees.

As shown in the following figure, any path from the leaf node to the root node is always a monotonous sequence.

The small top stack only needs to replace the above less than or equal to greater than or equal to.

4. Function

Or take the large top reactor as an example, the heap can obtain the element with the largest keyword in O (1) time. And can perform inserts and deletions within the time of O (log2n) O (log_2n) O (log2n). It is generally used to implement priority queues.

2. Storage structure of the heap

In the process of learning the heap, we can learn a new form of representation. That is: use arrays to represent chained structures. How do you understand this sentence?

Because the heap itself is a complete binary tree, we can map each node into a sequentially stored array, and then use the subscript of each node in the array to determine the relationship between nodes.

As shown in the figure, it describes the relationship between the heap node subscript and the node, and the numbers on the node represent the array subscript. It increases continuously from left to right in sequence.

1. Root node number

The number of the root node depends on the author's preference. You can use 0 or 1. The author of this article is from C language, so he is more likely to choose 0 as the number of the root node (because using 1 as the root node number, the 0th element of the array is wasted).

We can implement its definition with a macro definition, as follows:

# define root 02, Child Node number

Then, the numbers of the two left and right subtrees of the root node are 1 and 2, respectively. And so on, if numbered according to the sequence, the left and right subtrees of 1 are numbered 3 and 4, and the left and right subtrees of 1 are numbered 5 and 6.

According to mathematical induction, for the node numbered i i i, the left subtree is numbered 2i+1 2i+1 2i+1 and the right subtree is numbered 2i+2 2i+2 2i+2. The implementation with a macro definition is as follows:

# define lson (idx) (2*idx+1) # define rson (idx) (2*idx+2)

Since multiplication 2 is involved here, we can also use the left shift operation to optimize the multiplication operation, as follows:

# define lson (idx) (idx 1)

Here, using the property of the complement, the value obtained by the parent node of the root node is-1.

4. Data domain

Two data fields of heap data elements can be defined: keywords and values, where keywords are generally integers to facilitate comparison to determine the size relationship, while values are used for display and can be of any type, which can be defined with typedef struct as follows:

Typedef struct {int key; / / (1) void * any; / (2)} DataType

(1) keywords

(2) value, defined as a null pointer, can be used to represent any type

5. Data structure of the heap

Since the heap is essentially a complete binary tree, it must be continuous after mapping it to an array one by one. We can use an array to represent a heap. An array in C language has a fixed length, which can be represented by a Heap structure as follows:

Typedef struct {DataType * data; / / (1) int size; / / (2) int capacity; / (3)} Heap

(1) the first address of the array in which the heap element resides

(2) number of heap elements

(3) the maximum number of elements in the heap

Common interfaces of heap 1. Element comparison

The comparison of the two heap elements can be accomplished by a comparison function compareData. The comparison process is the process of comparing the keyword key. Take the big top heap as an example:

a. Greater than the return of-1, which means the exchange needs to be performed.

b. Less than 1 is returned, which means the exchange needs to be performed.

c. It is equal to 0, which means the exchange needs to be performed.

Int compareData (const DataType* a, const DataType* b) {if (a-> key > b-> key) {return-1;} else if (a-> key)

< b->

Key) {return 1;} return 0;} 2, exchange elements

Exchanging the position of two elements is also a common operation in the data structure of heap, and the implementation in C language is relatively simple, as follows:

Void swap (DataType* a, DataType* b) {DataType tmp = * a; * a = * b; * b = tmp;} 3, null decision

Null decision is a query interface that asks whether the heap is empty. The implementation is as follows:

Bool HeapIsEmpty (Heap * heap) {return heap- > size = = 0;} 4, full decision

Full decision is a query interface that asks whether the heap is full. The implementation is as follows:

Bool heapIsFull (Heap * heap) {return heap- > size = = heap- > capacity;} 5, floating operation

For the big top heap, the element keywords from its leaf node to the root node must be monotonous, and if an element is larger than its parent node, it needs to float.

The floating operation is to compare the current node with the parent node, and if its keyword is larger than the parent node (if compareData returns-1), exchange it with the parent node and continue the floating operation; otherwise, the floating operation is terminated.

As shown in the figure, it represents the process of reaching the root node through continuous floating of a node with the keyword 95. After surfacing, it is still a big top pile.

The C language implementation of the floating process is as follows:

Void heapShiftUp (Heap* heap, int curr) {/ / (1) int par = parent (curr); / / (2) while (par > = root) {/ / (3) if (compareData (& heap- > data [curr], & heap- > data [par])

< 0 ) { swap(&heap->

Data [curr], & heap- > data [par]); / / (4) curr = par; par = parent (curr);} else {break; / / (5)}}

(1) heapShiftUp is an internal interface, so it is distinguished by a lowercase hump to realize the floating operation when inserting elements in the heap.

(2) curr represents the number of nodes that need to float in the heap, and par represents the parent node number of curr.

(3) if it is already a root node, there is no need to float.

(4) if the keyword of the child node is greater than that of the parent node, the exchange is performed, and the new current node and parent node number are updated.

(5) otherwise, it means that the position has been returned correctly, the floating operation is over, and the cycle is jumped out.

6. Sinking operation

For the big top heap, the element keywords from its root node to the leaf node must be monotonous, and if an element is smaller than one of its child nodes, it needs to sink.

The sinking operation is to compare the current node with the sub-node with relatively small keywords. If its keyword is smaller than the sub-node, exchange it with the sub-node and continue the sinking operation; otherwise, the sinking operation is terminated.

As shown in the figure, it represents a node with the keyword 19 that sinks continuously to reach the leaf node. After sinking, it is still a big top pile.

The C language implementation of the sinking process is as follows:

Void heapShiftDown (Heap* heap, int curr) {/ / (1) int son = lson (curr); / / (2) while (son

< heap->

Size) {if (rson (curr))

< heap->

Size) {if (& heap- > data [Rson (curr)], & heap- > data [son])

< 0 ) { son = rson(curr); // (3) } } if( compareData( &heap->

Data [son], & heap- > data [curr])

< 0 ) { swap(&heap->

Data [son], & heap- > data [curr]); / / (4) curr = son; son = lson (curr);} else {break; / / (5)} void heapShiftDown (Heap* heap, int curr) {/ / (1) int son = lson (curr) / / (2) while (son

< heap->

Size) {if (rson (curr))

< heap->

Size) {if (& heap- > data [Rson (curr)], & heap- > data [son])

< 0 ) { son = rson(curr); // (3) } } if( compareData( &heap->

Data [son], & heap- > data [curr])

< 0 ) { swap(&heap->

Data [son], & heap- > data [curr]); / / (4) curr = son; son = lson (curr);} else {break; / / (5)}}

(1) heapShiftDown is an internal interface, so it is distinguished by a lowercase hump and is used to adjust the sinking when deleting elements in the heap.

(2) curr represents the heap number of the node that needs to be sunk, and son represents the node number of the left son of curr.

(3) always select sub-nodes with smaller keywords

(4) if the value of the child node is less than that of the parent node, the exchange is performed.

(5) otherwise, it means that you have returned to your position correctly, the sinking operation ends, and you jump out of the cycle.

4. Creation of heap 1. Description of algorithm

Create a heap from a given data set. You can first create the memory space of the heap array, and then perform the heap insert operation one by one. The specific implementation of the insert operation will be explained below.

2. Animation demonstration

3. Heap* HeapCreate (DataType * data, int dataSize, int maxSize) {/ / (1) int I; Heap* h = (Heap*) malloc (sizeof (Heap)); / / (2) h-> data = (DataType *) malloc (sizeof (DataType) * maxSize); / / (3) h-> size = 0 / / (4) h-> capacity = maxSize; / / (5) for (I = 0; I

< dataSize; ++i) { HeapPush(h, data[i]); // (6) } return h; // (7)} (1) 给定一个元素个数为dataSize的数组data，创建一个最大元素个数为maxSize的堆并返回堆的结构体指针； (2) 利用malloc申请堆的结构体的内存； (3) 利用malloc申请存储堆数据的数组的内存空间； (4) 初始化空堆； (5) 初始化堆最大元素个数为maxSize； (6) 遍历数组执行堆的插入操作，插入的具体实现HeapPush接下来会讲到； (7) 最后，返回堆的结构体指针； 五、堆元素的插入1、算法描述 堆元素的插入过程，就是先将元素插入堆数组的最后一个位置，然后执行上浮操作； 2、动画演示 3、源码详解bool HeapPop(Heap *heap) { if(HeapIsEmpty(heap)) { return false; // (1) } heap->

Data [root] = heap- > data [--heap- > size]; / / (2) heapShiftDown (heap, root); / / (3) return true;}

(1) the heap is full and cannot be inserted

(2) insert the last position of the heap array

(3) float the heap element in the last position

5. Deletion of heap elements 1. Algorithm description

For the deletion of heap elements, you can only operate on the heap top element. You can put the last element of the array on the heap top, and then sink the heap top element.

2. Animation demonstration

3. Bool HeapPop (Heap * heap) {if (HeapIsEmpty (heap)) {return false; / / (1)} heap- > data [root] = heap- > data [--heap- > size]; / / (2) heapShiftDown (heap, root); / / (3) return true;}

(1) the heap is empty and cannot be deleted

(2) putting the last element of the heap array on top of the heap is equivalent to deleting the element on the top of the heap.

(3) sinking the elements on the top of the heap

Thank you for reading! This is the end of the article on "how to solve the binary heap problem in C language". I hope the above content can be of some help to you, so that you can learn more knowledge. If you think the article is good, you can share it for more people to see!

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.