关于 php 通过链表为底层以及最大二叉堆为底层实现的优先队列运行时长的疑惑。
来源：8-6 基于堆的优先队列
我叫州皓辰
2018-11-06
bobo老师，我碰到了一个疑惑，我用php实现的最大二叉堆，插入1000个元素竟然要20s+。
然后我用最大二叉堆和链表分别实现了优先队列，测试了1000 数据量的插入和取出，通过堆实现的竟然花了32s，而通过链表实现的只花了0.2秒，这让我有一点不明白了。
代码位置：
链表底层实现 https://github.com/CoderChenHZ/data_structure/blob/master/Queue/Src/PriorityQueueByLinkedList.php
堆底层实现 : https://github.com/CoderChenHZ/data_structure/blob/master/Queue/Src/PriorityQueueByHeap.php
测试代码：https://github.com/CoderChenHZ/data_structure/blob/master/Queue/Test/TestPriorityQueue.php
麻烦 bobo 能够针对我的代码给我一点意见以及逻辑是否正确。
1回答
-
liuyubobobo
2018-11-07
优先队列不能基于链表实现，只能基于数组实现。因为优先队列是基于堆的，对于堆的操作来说，随机访问是非常重要的。
比如，以课程中介绍的ShiftUp操作为例：
private void siftUp(int k){ while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0 ){ data.swap(k, parent(k)); k = parent(k); } }在课程中，data的底层是动态数组，所以每一次get操作，都是O(1)的，整体这个操作是O(logn)的；
但如果data的底层是一个链表，每一次get操作将是O(n)的，整体这个操作将是O(nlogn)的！
请仔细体会一下，我们在讲堆的时候，设计的那个数组，到底是如何和堆的逻辑操作连接起来的：）
加油！：）
032018-11-08
相似问题