-1

我正在阅读 Magnus Lie Hetland 的《Python 从新手到专家》一书（第三版），并遇到了 Heaps。在那里，他讨论了堆列表的排序顺序，因为“元素的顺序很重要（即使它看起来有点随意......”

根据他的说法，堆算法有 2 条元素排序规则：

1) i处的元素大于位置i处的元素//2

如果没有制作，则：

2) 位置 i 的元素低于位置 2*i 和 2*i+1 的元素

我运行了一个代码检查这些规则，看看它们是否一直有效，

from heapq import *
from random import shuffle

data = list(range(10))
heap = []
shuffle(data)
for i in data:
    heappush(heap, i)
print(heap)
temp = False

#From p.240 
#The order of the elements isn’t as arbitrary as it seems. They aren’t in 
#strictly sorted order, but there is one
#guarantee made: the element at position i is always greater than the one 
#in position i // 2 (or, conversely,
#it’s smaller than the elements at positions 2 * i and 2 * i + 1). This is 
#the basis for the underlying heap
#algorithm. This is called the heap property.

for i in heap:
    print('___________')
    if heap[i] > heap[i//2]:
        print('First if: {}>{}'.format(heap[i],heap[i//2]))
        temp = True
        try:    
            if heap[i] < heap[2*i]:
                print('Second if: {}<{}'.format(heap[i],heap[i*2]))
                temp = True
        except IndexError:
                pass
        try:
            if heap[i] < heap[2*i+1]:
                print('Third if: {}<{}'.format(heap[i],heap[i*2+1]))
                temp = True
        except IndexError:
                pass
    else:
        try:    
            if heap[i] < heap[2*i]:
                print('Second if: {}<{}'.format(heap[i],heap[i*2]))
                temp = True
        except IndexError:
                pass
        try:
            if heap[i] < heap[2*i+1]:
                print('Third if: {}<{}'.format(heap[i],heap[i*2+1]))
                temp = True
        except IndexError:
                pass
    if not temp:
        print('No requirement was made')
    temp = False
    print('___________')

正如预期的那样，有些输入实现了目标，有些则没有，例如：

[0, 1, 2, 3, 5, 8, 7, 9, 4, 6]
[0, 3, 1, 5, 4, 6, 2, 7, 8, 9]

我的问题是，当这些规则都不适用时，是否还有更多的排序规则？

4

1 回答 1

1

如评论中所述，您拥有的规则在具有基于 1 的索引的数组框架中进行了说明。Python 列表是从 0 开始的，因此

如果一个孩子在 heap[i]，在 Python heap 中，父母在 heap[(i - 1) // 2]，而不是在 heap[i // 2]。相反，如果父节点位于 heap[j]，则其子节点位于 heap[j * 2 + 1] 和 heap[j * 2 + 2]

这很容易看出您是否真的花时间绘制堆：

   Example 1          Example 2         Python Index      1-based Index
       0                  0                  0                  1
   1       2          3       1          1       2          2       3
 3   5   8   7      5   4   6   2      3   4   5   6      4   5   6   7
9 4 6              7 8 9              7 8 9              8 9 A
于 2019-10-03T08:00:38.273 回答