heapsort en Python en ordre décroissant

Question

J'ai cherché et essayé beaucoup, mais je n'arrive pas à comprendre comment je peux trier une liste dans l'ordre décroissant en utilisant Heapsort. Et aussi je veux documenter mes calculs avec une commande d'impression afin de comprendre les chemins de calcul. Ceci est mon code qui fonctionne:

def swap(a, i, j): 
    a[i], a[j] = a[j], a[i] 

def is_heap(a): 
    n = 0 
    m = 0 
    while True: 
     for i in [0, 1]: 
      m += 1 
      if m >= len(a): 
       return True 
      if a[m] > a[n]: 
       return False 
     n += 1 

def sift_down(a, n, max): 
    while True: 
     biggest = n 
     c1 = 2*n + 1 
     c2 = c1 + 1 
     for c in [c1, c2]: 
      if c < max and a[c] > a[biggest]: 
       biggest = c 
     if biggest == n: 
      return 
     swap(a, n, biggest) 
     n = biggest 

def heapify(a): 
    i = len(a)/2 - 1 
    max = len(a) 
    while i >= 0: 
     sift_down(a, i, max) 
     i -= 1 

def sortHeapDesc(a): 

    heapify(a) 
    j = len(a) - 1 
    while j > 0: 
     swap(a, 0, j) 
     sift_down(a, 0, j) 
     j -= 1 
    return a 

liste = [3, 2, 1, 9, 17, 4, -1, 0] 
heapResult= sortHeapDesc(liste) 
print (heapResult) 

Et ce que je dois est comme que le résultat est le suivant: [17, 9, 4, 3, 2, 1, 0, -1]

Answer 1

ma fonction sortHeapDesc est un peu différent mais trie desc:

for i in range(start-1, 0, -1): # start -1 1 
    heapify(b, v, i) 

for i in range(v, -1, 1): # v-1 0 -1 
    chg(b, i, 0) 
    heapify(b, i, 0) 

Jetez un oeil à la fois pour les lignes. Le commentaire est pour asc et dans la gamme est desc actuellement mis en œuvre. Je peux vous donner mon code complet, si vous voulez.

Salutations.