Heap
Hu JiaJun edited this page Apr 22, 2021
·
6 revisions
优先队列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后面的元素都是叶结点