How to use the heap sort algorithm in C++

How to use the heap sort algorithm in C

Heap sort is a commonly used sorting algorithm that uses the properties of the heap for sorting. Heap sort is divided into two steps: heap building and sorting. In this article, we will learn how to implement the heap sort algorithm using C language and give specific code examples.

1. The definition and properties of heap
   Heap is a complete binary tree, which can be divided into two types: maximum heap and minimum heap. The value of any node in the max heap is greater than or equal to the value of its child nodes, and the value of any node in the min heap is less than or equal to the value of its child nodes. In heap sort algorithm, we usually use max heap.

The implementation of the heap can be represented by an array, and the subscript of the array can represent the node number in the heap. For any node i, its parent node is (i-1)/2, its left child node is 2i 1, and its right child node is 2i 2.

2. Heap building algorithm
   The heap building algorithm is the first step in heap sorting. Its purpose is to build an unordered array into a heap. The idea of ​​building a heap is to start from the last non-leaf node of the array and perform a sinking operation on each node so that it meets the properties of a heap.

The following is a C code example of the heap building algorithm:

// 下沉操作，将指定节点下沉到合适的位置
void downAdjust(int arr[], int parent, int length) {
    int child = 2 * parent + 1; // 左子节点的下标
    int temp = arr[parent]; // 保存要下沉的节点的值
    
    while (child < length) {
        // 如果有右子节点，且右子节点的值大于左子节点的值，则选择右子节点
        if (child+1 < length && arr[child] < arr[child+1]) {
            child++;
        }
        
        // 如果父节点的值大于等于子节点的值，则下沉结束
        if (temp >= arr[child]) {
            break;
        }
        
        // 将子节点的值上移，代替父节点
        arr[parent] = arr[child];
        parent = child;
        child = 2 * parent + 1;
    }
    
    // 将要下沉的节点插入合适的位置
    arr[parent] = temp;
}

// 建堆算法，将无序数组构建成最大堆
void buildHeap(int arr[], int length) {
    // 从最后一个非叶子节点开始，依次进行下沉操作
    for (int i = (length-2) / 2; i >= 0; i--) {
        downAdjust(arr, i, length);
    }
}

3. Sort algorithm
   After the heap building is completed, we can perform sorting operations. The idea of ​​sorting is to Take out the top element of the heap, exchange it with the element at the end of the heap, and then perform the sinking operation again on the remaining parts.

The following is a C code example of the heap sort algorithm:

// 堆排序算法
void heapSort(int arr[], int length) {
    // 1. 构建最大堆
    buildHeap(arr, length);
    
    // 2. 排序
    for (int i = length - 1; i > 0; i--) {
        // 将堆顶元素与堆尾元素交换
        swap(arr[i], arr[0]);
        
        // 对剩下的部分重新进行下沉操作
        downAdjust(arr, 0, i);
    }
}

4. Example and test
   The following is an example and test using the heap sort algorithm:

#include <iostream>

// 输出数组元素
void printArray(int arr[], int length) {
    for (int i = 0; i < length; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

// 主函数
int main() {
    int arr[] = {4, 1, 3, 9, 7};
    int length = sizeof(arr) / sizeof(int);
    
    std::cout << "排序前的数组：" << std::endl;
    printArray(arr, length);
    
    // 使用堆排序算法进行排序
    heapSort(arr, length);
    
    std::cout << "排序后的数组：" << std::endl;
    printArray(arr, length);
    
    return 0;
}

The output result is:

排序前的数组：
4 1 3 9 7 
排序后的数组：
1 3 4 7 9 

Through the above examples and tests, we can see that the heap sort algorithm implemented in C language can correctly sort the array.

Summary:
This article introduces how to use C language to implement the heap sort algorithm and gives specific code examples. The core of the heap sorting algorithm lies in the two steps of heap building and sorting. The idea of ​​building a heap is to start the sinking operation from the last non-leaf node. The idea of ​​sorting is to take out the top element of the heap each time and exchange it with the element at the end of the heap. , and re-sink the remaining parts. Through actual testing, we can verify the correctness and stability of the heap sort algorithm.

The above is the detailed content of How to use the heap sort algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!