Heap sorting golang implementation

Heap Sort is a common sorting algorithm based on the binary heap data structure. Its time complexity is O(nlogn) and can be used to handle large-scale data sorting problems. This article will introduce the implementation of heap sorting in golang.

1. Introduction to Heap Sorting

A heap is a complete binary tree, in which each node satisfies that the value of the parent node is greater than or equal to (or less than or equal to) the value of its child node, which is called Large root pile (or small root pile). Heap sort uses the characteristics of the heap to organize the elements to be sorted into a heap, and then removes the top elements of the heap one by one until the heap is empty to obtain an ordered result.

The following is a simple process of heap sorting:

1. Build an initial heap for the elements to be sorted, taking the large root heap as an example, that is, if the value of the current node is less than (or greater than or equal to) its child If the value of the node is changed, the positions of the two nodes are exchanged, so that after processing, the root node is the largest (or smallest) element.
2. Exchange the root node with the last element, and the largest element is placed at the end.
3. Rebuild the heap from the remaining elements, then take out the root node and place it at the end of the remaining elements.
4. Repeat 2 and 3 until the heap is emptied and the sorting is completed.

2. Code Implementation

The implementation of heap sorting requires the use of the idea of ​​a large root heap. We can use slices to store the heap. The following is the golang implementation of heap sorting:

func heapSort(arr []int) {
    length := len(arr)
    // 构建初始堆
    for i := (length - 2) / 2; i >= 0; i-- {
        heapify(arr, i, length)
    }
    // 逐个取出堆顶元素
    for i := length - 1; i > 0; i-- {
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, 0, i)
    }
}

func heapify(arr []int, index, length int) {
    left := 2*index + 1
    right := 2*index + 2
    maxIndex := index

    if left < length && arr[left] > arr[maxIndex] {
        maxIndex = left
    }

    if right < length && arr[right] > arr[maxIndex] {
        maxIndex = right
    }

    if maxIndex != index {
        arr[index], arr[maxIndex] = arr[maxIndex], arr[index]
        heapify(arr, maxIndex, length)
    }
}

In this code, the heapify function implements the construction and adjustment of the heap. We start from the last non-leaf node of the heap (that is, the parent node of the last node) and work our way up to the root node. For each node, we need to determine its size relationship with the left and right child nodes. If one of the left and right child nodes is larger than the parent node, then exchange the node with the parent node. After processing this once, the root node is the maximum value. In heap sorting, we take out the root node each time and place it in a position where the heap should be empty, and then build the heap again for the remaining elements.

In the main function, you only need to call the heapSort function to complete the sorting of the array:

func main() {
    arr := []int{5, 6, 7, 8, 1, 2, 3, 4, 0}
    fmt.Println(arr)
    heapSort(arr)
    fmt.Println(arr)
}

Output result:

[5 6 7 8 1 2 3 4 0]
[0 1 2 3 4 5 6 7 8]

3. Summary

Heap sort is an efficient sorting algorithm with a time complexity of O(nlogn). In golang, we can implement heap storage through slicing, and then build and adjust the heap through the heapify function. Compared with other sorting algorithms, heap sort consumes less memory and has faster calculation speed when processing large-scale data. At the same time, heap sorting is also unstable and is not suitable for situations where the relative order of elements is required to remain unchanged.

The above is the detailed content of Heap sorting golang implementation. For more information, please follow other related articles on the PHP Chinese website!