理解heapq排序算法

Question

我正在阅读 Magnus Lie Hetland 的 "Python from Novice to Expert" 这本书（第三版）并偶然发现了 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]

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

Answer 1

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

if a child is at heap[i], in Python heap the parent is at heap[(i - 1) // 2], not at heap[i // 2]. Conversely, if a parent is at heap[j], then its children are at heap[j * 2 + 1] and 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

理解heapq排序算法

Understanding heapq sorting algorithm

python

algorithm

sorting

heap

heapq