Heap - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki
入门链接
优先队列PriorityQueue,堆Heap【数据结构和算法入门8】 二叉堆(前半段) 二叉堆(前半段) 二叉堆(前半段)
图解
详解
什么是优先队列? Priority Queue:Intro(簡介) 漫画:什么是二叉堆?
优先队列的实现方式和时间复杂度
已排序数组 | 未排序数组 | AVL树 | 斐波那契堆 | |
---|---|---|---|---|
插入insert | O(n) | O(1) | O(logn) | |
查找最大extractMax | O(1) | O(n) | O(logn) | |
删除最小deleteMin | O(1) | O(n) | O(logn) | |
包含contains | O(1) | O(n) | O(logn) | |
降权decreaseKey | O(n) | O(1) | O(logn) |
构建堆 一边插入一边做堆化,或全部插入,再做堆化,详见上面的两个视频
要点
- 2 * parent + 1 和 2 * parent + 2
- 若n个结点储存在数组A中,最后一个存在子结点的元素a在(n-1)/2或(n-2)/2,即a之前的元素都有子结点,而a后面的元素都是叶结点