满足条件
- 需要是完全二叉树。除了最后一层，其他层是满的，最后一层都靠左排列。
- 每个节点的值必须大于等于(小于等于)其子树的每个节点的值
如何存储堆
使用数组
- 堆是完全二叉树，使用数组比较节省空间。因为不需要存储左右子孩子节点的指针
-
通过数组的下标就可以找到节点的父节点和左右孩子节点
image.png - 如果小标从1开始。下标是i,左节点是2*i,右节点是2*i+1.父节点下标是i/2
- 如果小标从0开始。如果节点的下标是i，那左子节点的下标就是2i+1，右子节点的下标就是2i+2，父节点的下标就是(i-1)/2
- 这里讲解和Demo都是从下标1开始
插入数据
- 把元素插入到最后一个位置
- 让插入的元素和父节点比较，如果不满足子节点小于等于夫节点，就互换节点。一直重复之到堆顶。从下向上堆化
-
时间复杂度O(logn)
image.png
image.png
func (heap *Heap) Insert(item int) error {
if heap.count >= heap.capacity {
return fmt.Errorf("heap is full")
}
heap.count++
//1. 放到最后
heap.array[heap.count] = item
i := heap.count
//从下向上堆化
//i/2:父节点 直到小于等于父节点,或者到了根节点
for i/2 > 0 && heap.array[i] > heap.array[i/2] {
swap(heap.array, i, i/2)
i = i / 2
}
return nil
}
删除堆顶元素
-
错误做法
直接删除堆顶元素，找出左右节点中大值，替换父节点。依次递归操作直到叶子节点。这样会造成不是一个完全二叉树。
image.png 正确做法
把最后一个节点放到堆顶，从上到下，依次递归比较和父子节点，如果不满足父子节点之间的关系，互换两个节点。知道父子节点满足大小关系。
因为我们是移除的最后的一个节点，在堆化操作中都是互换，不会出现数组空洞，堆化完成肯定满足完全二叉树-
时间复杂度O(logn)
image.png
func (heap *Heap) RemoveRoot() error {
if heap.count <= 0 {
return fmt.Errorf("heap is empty")
}
//1.把最后一个节点赋值个根节点
heap.array[1] = heap.array[heap.count]
heap.array[heap.count] = 0
heap.count--
heapify(heap.array, heap.count, 1)
return nil
}
/**
从上向下堆化
*/
func heapify(slice []int, count int, startIndex int) {
for {
maxIndex := startIndex
//节点和自己的左右节点比较,找出最大的
if startIndex*2 <= count && slice[maxIndex] < slice[startIndex*2] {
maxIndex = startIndex * 2
}
if startIndex*2+1 <= count && slice[maxIndex] < slice[startIndex*2+1] {
maxIndex = startIndex*2 + 1
}
if maxIndex == startIndex {
//发现节点已经比自己左右节点大了，堆化完成
break
}
//交互节点数据
swap(slice, startIndex, maxIndex)
//继续向下堆化
startIndex = maxIndex
}
}
在原有数组上建堆
- 在数组上从后向前
- 从上向下堆化
- 叶子节点向下堆化只能和自己比较，叶子节点不参与
-
时间复杂度O(n)
image.png
image.png
func BuildHeap(array []int, count int) *Heap {
heap := NewHeap(count)
//把数组转换成从1开始
for i := 0; i < count; i++ {
heap.array[i+1] = array[i]
}
//从非叶子节点开始(叶子节点向下堆化只能和自己比较没有意义)，从上向下堆化。直到根节点(包含)
//堆是完全二叉树，所以count / 2之后的节点都是叶子节点
for i := count / 2; i >= 1; i-- {
heapify(heap.array, count, i)
}
return heap
}
堆排序
- 建堆
- 堆顶元素和最后一个元素互换，最大值就到了最后。然后对n-1的堆进行进行从节点开始从上向下进行堆化。完成后把堆顶元素和n-1进行互换。重复上面的步骤一直到只有一个元素。就完成了排序
- 时间复杂度O(nlogn)
- 不稳定
func Sort(slice []int, count int) []int {
//1. 建堆
heap := BuildHeap(slice, count)
for k := count; k > 1; {
//2. 每次都把堆顶元素移动到最后
swap(heap.array, 1, k)
k--
//3. 堆化剩余的元素，直到剩下一个元素
heapify(heap.array, k, 1)
}
return heap.array
}
/**
从上向下堆化
*/
func heapify(slice []int, count int, startIndex int) {
for {
maxIndex := startIndex
//节点和自己的左右节点比较,找出最大的
if startIndex*2 <= count && slice[maxIndex] < slice[startIndex*2] {
maxIndex = startIndex * 2
}
if startIndex*2+1 <= count && slice[maxIndex] < slice[startIndex*2+1] {
maxIndex = startIndex*2 + 1
}
if maxIndex == startIndex {
//发现节点已经比自己左右节点大了，堆化完成
break
}
//交互节点数据
swap(slice, startIndex, maxIndex)
//继续向下堆化
startIndex = maxIndex
}
}
和快排的比较
- 堆排的数据读取开销比较大
对于快排，数据是顺序访问的。对于堆排，数据是跳的访问的。
在计算机进行运算的时候，数据不一定会从内存读取出来，而是从一种叫cache的存储单位读取。原因是cache相比内存，读取速度非常快，所以cache会把一部分我们经常读取的数据暂时储存起来，以便下一次读取的时候，可以不必跑到内存去读，而是直接在cache里面找。一般认为读取数据遵从两个原则：temporal locality，也就是不久前读取过的一个数据，在之后很可能还会被读取一遍；另一个叫spatial locality，也就是说读取一个数据，在它周围内存地址存储的数据也很有可能被读取到。因此，在读取一个单位的数据(比如1个word)之后，不光单个word会被存入cache，与之内存地址相邻的几个word，都会以一个block为单位存入cache中。
为什么在平均情况下快速排序比堆排序要优秀
- 对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序
我们在讲排序的时候，提过两个概念，有序度和逆序度。对于基于比较的排序算法来说，整个排序过程就是由两个基本的操作组成的，比较和交换（或移动）。
快速排序数据交换的次数不会比逆序度多。
但是堆排序的第一步是建堆，建堆的过程会打乱数据原有的相对先后顺序，导致原数据的有序度降低。比如，对于一组已经有序的数据来说，经过建堆之后，数
据反而变得更无序了
