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

This article mainly explains "how to achieve heap sorting on C++". The content in the article is simple and clear, and it is easy to learn and understand. Please follow the editor's ideas slowly and deeply. Let's study and learn "how to achieve heap sorting on C++".

A preparation of knowledge

The structure of the heap can be divided into large root heap and small root heap, which is a complete binary tree. Heap sorting is a sort designed according to this data structure of the heap. Let's take a look at what big root heap and small root heap are.

1.1 Big Root pile and small Root pile

Properties: the value of each node is greater than the value of its left and right child nodes, which is called large root heap; the value of each node is less than the value of its left and right child nodes, which is called small root heap. The figure below is as follows

We marked each number in the above figure, and the structure above was mapped into an array and it looked like this.

There is also a basic concept: to find the parent node and the left and right child nodes of a number in the array, such as a number with a known index I, then

1. Parent node index: (iMur1) / 2 (here the computer is divided by 2, omitting the decimal)

two。 Left Child Index: 2*i+1

3. Right Child Index: 2*i+2

So the above two arrays can be added to the heap structure because they satisfy the defined properties of the heap:

Big root heap: arr (I) > arr (2i+1) & & arr (I) > arr (2i+2)

Small root heap: arr (I) arr (0), then swap; in this case, the position of 0x2 is guaranteed to be a large root heap structure, as shown in the following figure

When inserting 5, 5 is larger than its parent node 3, then the exchange, after the exchange, 5 is found to be smaller than 8, so it is not exchanged; at this time, the large root heap structure at position 0 to 3 is guaranteed, as shown in the following figure

When 7 is inserted, 7 is greater than its parent node 5, then exchange, after exchange, 7 is found to be smaller than 8, so it is not exchanged; at this time, the whole array is already a large root heap structure.

2.2 fixed maximum reconstruction heap

At this point, we have got a large root heap, and then swap the top number with the last digit, and then construct the remaining number into a large root heap.

(friendly reminder: black is a fixed number, no longer participate in sorting)

At this time, the maximum number of 8 has come to the end, then it is fixed, and then you only need to operate the data at the top. Compare the number at the top with the larger number of children around. If the number at the top is greater than the larger number of children around, stop, if the number at the top is less than the larger number of children around, exchange, and then continue to compare with the following children.

In the following picture, among the children of about 5, the left child 7 is older than the right child 6, then 5 is compared with 7, and it is found that 51) {/ / fixed maximum swap (arr, 0, size- 1); size--; / / construct large root heap heapify (arr, 0, size) }} / / construct a large root heap (rising by newly inserted numbers) public static void heapInsert (int [] arr) {for (int I = 0; I)

< arr.length; i++) { //当前插入的索引 int currentIndex = i; //父结点索引 int fatherIndex = (currentIndex - 1) / 2; //如果当前插入的值大于其父结点的值,则交换值，并且将索引指向父结点 //然后继续和上面的父结点值比较，直到不大于父结点，则退出循环 while (arr[currentIndex] >

Arr [fatherIndex]) {/ / Exchange the values of the current node and the parent node swap (arr, currentIndex, fatherIndex); / / point the current index to the parent index currentIndex = fatherIndex; / / recalculate the parent index of the current index fatherIndex = (currentIndex-1) / 2 } / / construct the remaining number into a large root heap (reduced by the number at the top) public static void heapify (int [] arr, int index, int size) {int left = 2 * index + 1; int right = 2 * index + 2; while (left

< size) { int largestIndex; //判断孩子中较大的值的索引（要确保右孩子在size范围之内） if (arr[left] < arr[right] && right < size) { largestIndex = right; } else { largestIndex = left; } //比较父结点的值与孩子中较大的值，并确定最大值的索引 if (arr[index] >

Arr [largestIndex]) {largestIndex = index;} / / if the parent node index is the largest index, which is already a large root heap, exit the loop if (index = = largestIndex) {break } / / the parent node is not the maximum value, exchange swap (arr, largestIndex, index) with the larger value in the child; / / the index pointing to the larger value in the child index = largestIndex; / / recalculate the child's index left = 2 * index + 1; right = 2 * index + 2 The values of two elements in the exchange array public static void swap (int [] arr, int I, int j) {int temp = arr [I]; arr [I] = arr [j]; arr [j] = temp } Thank you for your reading. the above is the content of "how to achieve heap sorting on C++". After the study of this article, I believe you have a deeper understanding of the problem of how to achieve heap sorting on C++. The specific use also needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

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.