目录
- 350-两个数组的交集
- 283-移动零
- 1-两数之和
- 25-K 个一组翻转链表
- 581-最短无序连续子数组
- 合并区间
- 螺旋矩阵
- 数组中相加和为0的三元组
- 数组中出现次数超过一半的数字
- 字符串出现次数的TopK问题
- 206-反转链表
- 160-相交链表
- 19-删除链表的倒数第N个节点
- 21-合并两个有序链表
- 31-下一个排列
- 链表K位翻转
- 链表排序-归并算法
- 判断链表中是否有环
- 设计LRU缓存结构
- 两个链表的第一个公共结点
- 两个链表生成相加链表
- 合并N个有序链表
- 链表内指定区间反转
堆排序
访问量:1503
一、什么是堆
堆,是完全二叉树,被称为优先级队列。
分最大堆和最小堆,最大堆中任意节点的值大于或等于它的左、右子节点值,最小堆中任意节点的值小于或等于它的左、右子节点值。
这种数据结构的插入和删除操作,都需要o(lgn)的时间复杂度,但是取最大值和最小值的复杂度为o(1).
堆一般采用数组来存在,满足如下规则:
若堆存储在数组 arr中,当前元素的索引为i,那么
1.左子节点为 2*i+1
2.右子节点为 2*i+2
2.父节点为 (i-1)/2 向下取整
3.arr中0~arr.length/2-1 为非叶子节点,arr.length/2-1 ~ arr.length为叶子节点
因为堆是完全二叉树,故满足以下特性
n0: 度为0,即为叶子节点数量
n1: 度为1,即为只有左子树或者右子树的节点数量,但完全二叉树,度为1节点,只能是只有左子树。
n2:度为2,即有左右节点的节点数量
n0 = n2 + 1
叶子节点为 n/2 向上取整,或者(n+1)/2 向下取整
二、如何构建堆
构建最大堆
func MaxHeap(data []int) []int { if len(data) < 2 { return data } // 从 (n+1)/2个位置开始 curIndex := (len(data) + 1) / 2 -1 for i := curIndex ; i>=0; i-- { jumpMaxHeap(data, i) } return nil } func jumpMaxHeap(data []int, index int) { leftIndex := 2*index + 1 rightIndex := 2*index + 2 // 无子节点,不需要处理 if leftIndex >= len(data) { return } // 无右子节点,进行需要比较 左子节点 if rightIndex >= len(data) { if data[leftIndex] <= data[index] { return } // 交换 data[leftIndex], data[index] = data[index], data[leftIndex] // 递归 判断 jumpMaxHeap(data, leftIndex) return } // 从leftIndex,rightIndex,index中找出最大值,作为根元素 if data[index] >= data[leftIndex] && data[index] >= data[rightIndex] { // 根节点已是最大值,不需要处理 return } if data[leftIndex] > data[index] && data[leftIndex] >= data[rightIndex] { // 左子节点已是最大值,和跟节点交换 // 交换 data[leftIndex], data[index] = data[index], data[leftIndex] // 递归 判断 jumpMaxHeap(data, leftIndex) return } if data[rightIndex] > data[index] && data[rightIndex] > data[leftIndex] { // 右子节点已是最大值,和跟节点交换 // 交换 data[rightIndex], data[index] = data[index], data[rightIndex] // 递归 判断 jumpMaxHeap(data, rightIndex) return } }
以数组[1,3,5,7,4,6]图解如下:
二、堆排序
func heapSort(data []int) { // 1. 构建最大堆 MaxHeap(data) // index 代表已经排序了多少个元素 // 已经排序的元素,防止最最后的位置 for index := 0; index < len(data); index ++ { // 将最大堆的,堆顶元素,防止到最后位置 lastIndex := len(data) - index -1 data[lastIndex], data[0] = data[0], data[lastIndex] // 重新排序堆(0~n-index)个节点 leftHeap := data[:len(data) - index - 1] jumpMaxHeap(leftHeap, 0) } }
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助