堆排序 golang_golang 堆排序

堆排序

堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
在堆排序的时候会二叉堆 和树有相似的定义
- 父节点的键值大于等于(小于等于[最小堆])子节点
每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）

时间复杂度以及使用

时间复杂度为：O(N*logN) 和快排 归并排序相同。
使用场景：在一个大数组n中取top m 的问题上，经常维护一个m大小的堆。相比于先排序复杂度为O(N*logN)，这种堆排序的复杂度为O(N*logM)，更加低。并且在内存的消耗上也仅仅是m，比快排的n要更优。

堆的存储

堆的存储一般都是以一维数组作为存储。
在这个时候
1. 父节点i的左子节点在位置 (2i+1);
2. 父节点i的右子节点在位置(2i+2);
3. 子节点i的父节点在位置 floor((i-1)/2);

堆操作

堆有三种基本操作，通过这三种操作去做堆排序。

• 最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
• 创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
• 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

堆排序紧紧围绕这三种操作进行
创建堆 - > 取出最大元素 交换到最末尾 - > 调整堆
通过以上三种操作达到堆排序的目的

操作 - 堆排序

堆排序分两个关键的步骤

1. 创建堆 buildHeap
2. 取出堆堆顶元素 重新维护堆

func HeapSort(arr []int) {

    arrLen := len(arr)
    buildHeap(arr, arrLen)

    for i := arrLen - 1; i > 0; i-- {
        arr[0], arr[i] = arr[i], arr[0] //交换到最末尾的位置
        heapModify(arr, 0, i-1)         // 因为第0个元素已经被交换 所以需要调整第0个元素 i 已经有序 end改为i-1
    }
}
1
2
3
4
5
6
7
8
9
10

操作 - 构造堆

构造堆其实就是把一堆乱七八糟的数字调位以达到堆的定义，看定义就是保证父节点大于两个子节点就ok了。为了保证这一点必须从 n / 2 -1 最大的父节点开始保证，比如有一n层的树形结构，只要树下n-1层达到目标，那么新加入的元素只要调整自己合适的位置即可，不会影响原先的位置。

func buildHeap(arr []int, arrLen int){
    //初始化堆 构建一个堆 从最后一个父节点开始调整
    for father := (arrLen / 2) - 1; father >= 0; father-- {
        heapModify(arr, father, arrLen-1)
    }
}
1
2
3
4
5
6

操作 - 最大堆调整

所谓最大堆的调整就是一个 下沉 的过程。当前节点 也就是父节点和子节点中较大的那个做比较，如果小于它则做交换。下沉一个之后可能还会影响新的值，所以把子节点改为新的父节点，继续调整。

为什么是和较大的那个交换？
为了保证父节点比子节点大，只有和子节点中较大的那个作交换才能保证。当然这里要做越界校验。

/*
    调整堆
    调整节点 父节点如果小于最大的子节点则交换
    子节点设置为父节点 继续遍历
*/
func heapModify(arr []int, father, end int) {

    son := father*2 + 1

    for son <= end { //若子節點指標在範圍內才做比較
        if son+1 <= end && arr[son] < arr[son+1] { // 右子节点未越界 并且大于左子节点时 son设置为右子节点
            son++
        }

        if arr[father] > arr[son] { //无需交换
            return
        }

        arr[father], arr[son] = arr[son], arr[father] //交换

        father = son //向下移动一位 继续做判断
        son = father*2 + 1
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

测试

var testArr = []int{2,3,1,9,7,6,5,24,34,17}

func TestHeapSort(t *testing.T) {
    fmt.Printf("before Heap Sort: %+v \n", testArr)
    HeapSort(testArr)
    fmt.Printf("before Heap Sort: %+v \n", testArr)
}
1
2
3
4
5
6
7
8
9

结果

before Heap Sort: [2 3 1 9 7 6 5 24 34 17] 
before Heap Sort: [1 2 3 5 6 7 9 17 24 34] 
1
2

关于top n

很简单可以想到我们需要维护一个最大的数组，每个值和最大数组中最小的比较，如果大于它则需要替换掉数组中最小的元素。这不就是堆吗!!!堆排序很好的满足了这一点啊，于是我们可以这么做：

比如在一千万个数中找最大的m个。

1. 取前m个数字，构造一个最小堆。
2. 取第m+1个数字和最小堆堆顶做比较，如果大于它，插入新元素。删除堆顶元素。
3. 重复步骤二 从m+1 -> n.
4. 输出最小堆中的元素。

增加代码如下 未经测试

/*
    插入新元素相当于是在末尾增加元素 为了满足堆的性质 上浮操作
*/
func heapUp(arr []int, value int){

    arr = append(arr, value) // 新增元素
    arrLen := len(arr)

    son := arrLen -1
    if son > 1 && arr[son/2] < arr[son]{
        arr[son], arr[son/2] = arr[son/2], arr[son] //是否到根节点了，或者父节点比当前节点小
        son = son / 2
    }
}

/*
删除顶上元素时，取出该顶上元素（根节点），
然后把当前堆的最后一个元素临时放在根节点上，
然后使用Down来恢复堆的条件。
*/

func deleteTop(arr []int) (topValue int){
    arr[len(arr) -1], arr[0] = arr[0], arr[len(arr) -1]

    topValue = arr[0]

    arr = arr[:len(arr)-1]
    heapModify(arr,0,len(arr)-1)

    return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31