关于 php 通过链表为底层以及最大二叉堆为底层实现的优先队列运行时长的疑惑。

Question

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 能够针对我的代码给我一点意见以及逻辑是否正确。

Answer 1

liuyubobobo 2018-11-07 10:45:26

优先队列不能基于链表实现，只能基于数组实现。因为优先队列是基于堆的，对于堆的操作来说，随机访问是非常重要的。

比如，以课程中介绍的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)的！

请仔细体会一下，我们在讲堆的时候，设计的那个数组，到底是如何和堆的逻辑操作连接起来的：）

加油！：）

• 提问者 我叫州皓辰 #1

  bobo 老师，您上面说的情况都是队列基于堆的情况，我能够理解的。
  但是我这里说的通过以链表为底层实现的队列的意思是直接基于链表而不是堆呢。
  
  针对底层为链表实现的优先队列入队的时间复杂度应该是O(n),
  然后通过堆为底层实现的优先队列入队时间复杂度应该是O(logn)。
  
  但是我自己将这两种不同实现的优先队列做测试，发现同通过链表为底层的优先队列的测试运行时间竟然远远大于通过堆实现的队列的测试运行时间。这就让我有一点不理解了。我现在有一点怀疑是 php 的原因了，因为测试了一下往我自己实现的最大二叉堆中添加1000个元素，要花30s+。

• liuyubobobo 回复 提问者 我叫州皓辰 #2

  我可能没有特别理解你的意思。有可能是PHP的原因，脚本语言本身就不适合用来考察底层算法和数据结构实现的性能，这一点我在课程的第一章有提及。因为脚本语言的性能过度依赖解释器，使得同样的逻辑，怎么写变得很重要（而不仅仅是逻辑本身是什么）。但是同向对比，有这么大的差异，我怀疑在实现上有巨大的可以使用语言特性可以改进的空间，甚至可能实现有一定的问题。不过我不很熟悉PHP，在语言特性上无法提供更多帮助了:-( 加油！

• 提问者 我叫州皓辰 回复 liuyubobobo #3

  谢谢老师，:)