为什么会用balanced binary heap, 又有什么好处, 对design queue, deque 类似的题目又有什么启发?
这个是从geekForGeek 上面参考的, https://www.geeksforgeeks.org/why-is-binary-heap-preferred-over-bst-for-priority-queue/。 主要是从一下priorityQueue 主要用途的time complexity上面分析的
Get Top Priority Element (Get minimum or maximum) O(1)
Insert an element O(Logn)
Remove top priority element O(Logn)
Decrease Key O(Logn)
Queue 作为interface, extends the Collection interface, 需要a concrete class during declaration. 最常见的implementation 比如: PriorityQueue 和 LinkedList.
在视频中, 老师提到PriorityQueue 的具体实现可以有 bst, heap, 还有treap。 java源码里面用了a balanced binary heap. Binary heap 用的是数组表示。
为什么会用balanced binary heap, 又有什么好处, 对design queue, deque 类似的题目又有什么启发? 这个是从geekForGeek 上面参考的, https://www.geeksforgeeks.org/why-is-binary-heap-preferred-over-bst-for-priority-queue/。 主要是从一下priorityQueue 主要用途的time complexity上面分析的 Get Top Priority Element (Get minimum or maximum) O(1) Insert an element O(Logn) Remove top priority element O(Logn) Decrease Key O(Logn)