Понимание алгоритма сортировки heapq - PullRequest
Новая
       51

Понимание алгоритма сортировки heapq

0 голосов
/ 03 октября 2019

Я читаю книгу Магнуса Ли Хетланда "Питон от новичка до эксперта" (третье издание) и натолкнулся на Кучи. Там он обсуждает порядок сортировки списка кучи как «порядок элементов важен (даже если он выглядит немного случайным ..»

По его словам, алгоритм кучи имеет 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]

Мой вопрос: есть ли еще правила для сортировки, когда ни одно из этих правил не применимо?

1 Ответ

1 голос
/ 03 октября 2019

Как уже упоминалось в комментариях, ваше правило указано в рамках массивов с индексами на основе 1. Списки Python основаны на 0, и поэтому

, если дочерний элемент находится в куче [i], в куче Python родительский элемент находится в куче [(i - 1) // 2], а не в куче[я // 2]. И наоборот, если родитель находится в куче [j], то его дети находятся в куче [j * 2 + 1] и куче [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
...