最小堆自定义函数的时间复杂度高于预期

Question

我正在尝试在 python 中实现自定义最小堆。我想将元组存储在堆中，并根据元组中的第二个元素对它们进行排序。这是我的尝试：-

class minheap():
  def __init__(self):
      self.heap = list()
  def parent(self,i):
    return (i-1)//2
  def left_child(self,i):
    return 2*i+1
  def right_child(self,i):
    return 2*i+2

  def insert(self,l,i):
    h = self.heap
    h.append((l,i))
    j=len(h)-1
    while j>0:
      if h[self.parent(j)][1] > h[j][1]:
        j = self.parent(j)
      else:
        h[self.parent(j)] , h[j] = h[j] , h[self.parent(j)]
        break
    return
  
  def delmin(self):
    h = self.heap
    h[0], h[-1] = h[-1], h[0]
    m = h.pop(-1)
    j=0
    while True:
      if self.left_child(j) > len(h)-1:
        break
      if h[self.left_child(j)][1] < h[j][1]:
        h[self.left_child(j)], h[j] = h[j], h[self.left_child(j)]
        j = self.left_child(j)
      if self.right_child(j) > len(h)-1:
        break
      elif h[self.right_child(j)][1] < h[j][1]:
        h[self.right_child(j)], h[j] = h[j], h[self.right_child(j)]
        j = self.right_child(j)
      else:
        break
    return m

我测试了插入和删除所花费的时间，似乎每一个的复杂度都是O(logn)。这些是我为他们每个人记录的时间，n表示list(range(n))转换为堆：-

插入

Size(n)	Time
10000	0.01562
100000	0.06099
1000000	0.62161

Delmin

Size(n)	Time
10000	0.02703
100000	0.15629
1000000	1.22780

我也用过 heapq 函数创建了一个堆，虽然只有数字，但它们花费的时间要少得多。

heappush

Size(n)	Time
10000	0.0
100000	0.00800
1000000	0.08599

heappop

Size(n)	Time
10000	0.00199
100000	0.02472
1000000	0.28575

你能告诉我为什么自定义函数比默认包中的函数慢得多吗？

添加元组而不是数字是减慢过程的主要因素还是我的算法有问题导致此处出现问题？

Answer 1

您的算法的复杂性没有任何问题（注意在 1e6 而不是 1e5 值上运行时增加时间的近似因子 10）。标准库函数只是快了一个常数因子。这可能是因为它们经过优化，甚至可能是用编译语言编写的，可以运行快得多。

最小堆自定义函数的时间复杂度高于预期

Time complexity higher than expected for min-heap custom functions

python

data-structures

heap

min-heap