二叉堆与堆排序
二叉堆是一组能够用堆有序的完全二叉树排序的元素,一般用数组来存储。
大顶堆, 每个结点的值都大于或等于其左右孩子结点的值,其顶部为最大值。
小顶堆,每个结点的值都小于或等于其左右孩子结点的值,其顶部为最小值。
二叉堆
性质
- 根节点在数组中的位置是 1
- 左边子节点 2i
- 右子节点 2i+1
- 父节点 i / 2
- 最后一个非叶子节点为 len / 2
- 根节点在数组中的位置是 0
- 左子节点 2i + 1
- 右边子节点 2i+ 2
- 父节点的下标是 (i − 1) / 2
- 最后一个非叶子节点为 len / 2 - 1
图片来自知乎
实现
构造二叉堆
- 找到最后一个非叶子节点 ( len / 2 或者 len / 2 - 1)
- 从最后一个非叶子节点下标索引开始递减,逐个下沉
插入节点
- 在数组的最末尾插入新节点
- 将最后一个节点上浮,时间复杂度为O(log n)
- 比较当前节点与父节点
- 不满足 堆性质* *则交换
删除根节点
删除根节点用于堆排序
对于最大堆,删除根节点就是删除最大值;
对于最小堆,是删除最小值。
- 交换根节点和最后一个节点
- 将此时的根节点下沉,时间复杂度为O(log n)
- 比较当前节点与子节点(左,右)
- 不满足 堆性质 则交换
- 删除最后一个节点
代码
https://github.com/Allenxuxu/dsa/blob/master/heap/heap.go
代码 来源 go 标准库 ,少量修改提高可读性
package heap import "sort" type Interface interface { sort.Interface Push(x interface{}) // add x as element Len() Pop() interface{} // remove and return element Len() - 1. } // Init establishes the heap invariants required by the other routines in this package. // Init is idempotent with respect to the heap invariants // and may be called whenever the heap invariants may have been invalidated. // The complexity is O(n) where n = h.Len(). func Init(h Interface) { // heapify n := h.Len() for i := n/2 - 1; i >= 0; i-- { down(h, i, n) } } // Push pushes the element x onto the heap. // The complexity is O(log n) where n = h.Len(). func Push(h Interface, x interface{}) { h.Push(x) up(h, h.Len()-1) } // Pop removes and returns the minimum element (according to Less) from the heap. // The complexity is O(log n) where n = h.Len(). // Pop is equivalent to Remove(h, 0). func Pop(h Interface) interface{} { n := h.Len() - 1 h.Swap(0, n) down(h, 0, n) return h.Pop() } // Remove removes and returns the element at index i from the heap. // The complexity is O(log n) where n = h.Len(). func Remove(h Interface, i int) interface{} { n := h.Len() - 1 if n != i { h.Swap(i, n) // 如果此节点不需要下沉,则尝试上浮 if !down(h, i, n) { up(h, i) } } return h.Pop() } // Fix re-establishes the heap ordering after the element at index i has changed its value. // Changing the value of the element at index i and then calling Fix is equivalent to, // but less expensive than, calling Remove(h, i) followed by a Push of the new value. // The complexity is O(log n) where n = h.Len(). func Fix(h Interface, i int) { if !down(h, i, h.Len()) { up(h, i) } } func up(h Interface, j int) { for { parent := (j - 1) / 2 if parent == j || h.Less(parent, j) { break } h.Swap(parent, j) j = parent } } func down(h Interface, i0, n int) bool { i := i0 for { left := 2*i + 1 if left >= n || left < 0 { // j1 < 0 after int overflow break } toCompare := left // left child if right := left + 1; right < n && h.Less(right, left) { // 如果右节点比左节点小,则直接用右节点去比较 toCompare = right // = 2*i + 2 // right child } if h.Less(i, toCompare) { break } h.Swap(i, toCompare) i = toCompare } return
堆排序
堆排序是借助“堆”这种数据结构进行排序的排序算法。
实现
- 将原数组构造成堆
- 将堆顶元素和数组最后一个元素交换,然后执行下沉操作修复堆(此时修复的堆长度-1,最后一个元素用来存放有序数据)
- 重复上述步骤,直至堆为空
代码
https://github.com/Allenxuxu/dsa/blob/master/sort/heapsort.go
type Interface interface { // Len is the number of elements in the collection. Len() int // Less reports whether the element with // index i should sort before the element with index j. Less(i, j int) bool // Swap swaps the elements with indexes i and j. Swap(i, j int) } func down(data Interface, root, n int) { for { child := 2*root + 1 // left child if child >= n { break } if child+1 < n && data.Less(child, child+1) { // right = child+1 child++ } if data.Less(child, root) { return } data.Swap(root, child) root = child } } func HeapSort(data Interface) { n := data.Len() // Build heap with greatest element at top. for i := n/2 - 1; i >= 0; i-- { down(data, i, n) } // Pop elements, largest first, into end of data. for i := n - 1; i >= 0; i-- { data.Swap(0, i) down(data, 0, i) }
应用
堆排序是唯一能够同时最优化的利用空间和时间的方法 -- 在最坏的情况下也能保证使用 2NlogN 次比较和恒定额外空间。
但是,现代系统中许多应用很少使用它,因为它无法利用缓存 -- 数组元素很少和相邻的元素进行比较。因此缓存命中次数远低于在相邻元素进行比较的算法,如快速排序,归并排序,甚至是希尔排序。
标题:二叉堆与堆排序
作者:Allenxuxu
地址:https://mogutou.xyz/articles/2020/05/30/1590811456517.html
Github: https://github.com/Allenxuxu
转载请注明出处