Exemples de code pour implémenter le tas binaire et le tri des tas en Python

L'éditeur suivant vous apportera un exemple d'implémentation de tas binaire et de tri de tas en python. L'éditeur le trouve plutôt bon, je vais donc le partager avec vous maintenant et le donner comme référence pour tout le monde. Suivons l'éditeur pour y jeter un œil.

Le tas est une structure arborescente spéciale, et le stockage des données dans le tas satisfait à un certain ordre de tas. Le tri par tas est un tri par sélection, et sa complexité algorithmique et temporelle présente de grands avantages par rapport aux autres algorithmes de tri.

Les tas sont divisés en tas à grosse tête et en tas à petite tête. Comme son nom l'indique, le premier élément du tas à grosse tête est le plus grand. Chaque nœud parent avec des nœuds enfants a une valeur de données supérieure à. celle de ses nœuds enfants. La valeur des points doit être grande. Xiaotou Dui est le contraire.

Je vais expliquer brièvement le processus algorithmique de construction d'un tas d'arbre :

Trouvez les données du tableau à la position N/2, à partir de ceci position , recherchez l'index du nœud enfant gauche du nœud, comparez d'abord les nœuds enfants sous ce nœud, trouvez le plus grand, attribuez l'index du nœud enfant le plus grand au nœud enfant gauche, puis attribuez le nœud enfant le plus grand. le point est comparé au nœud parent. S'il est plus grand que le nœud parent, les données sont échangées avec le nœud parent. Bien sûr, je viens de parler brièvement de la mise en œuvre. Au cours de ce processus, nous devons également considérer la situation dans laquelle le nœud n'existe pas.

Regardez le code :

# 构建二叉堆 
def binaryHeap(arr, lenth, m): 
 temp = arr[m] # 当前结点的值 
 while(2*m+1 < lenth): 
 lchild = 2*m+1 
 if lchild != lenth - 1 and arr[lchild] < arr[lchild + 1]: 
 lchild = lchild + 1 
 if temp < arr[lchild]: 
 arr[m] = arr[lchild] 
 else: 
 break 
 m = lchild 
 arr[m] = temp 
 
 
def heapsort(arr, length): 
 i = int(len(arr)/2) 
 while(i >= 0): 
 binaryHeap(arr, len(arr), i) 
 i = i - 1 
 
 print("二叉堆的物理顺序为:") 
 print(arr) # 输出二叉堆的物理顺序 
 
 
if __name__ == &#39;__main__&#39;: 
 arr = [2, 87, 39, 49, 34, 62, 53, 6, 44, 98] 
 
 heapsort(arr, len(arr))

Le processus de tri des tas consiste à trier le dernier nœuds en séquence Comparez et échangez avec le premier nœud :

# 构建二叉堆
def binaryHeap(arr, lenth, m):
  temp = arr[m] # 当前结点的值
  while(2*m+1 < lenth):
    lchild = 2*m+1
    if lchild != lenth - 1 and arr[lchild] < arr[lchild + 1]:
      lchild = lchild + 1
    if temp < arr[lchild]:
      arr[m] = arr[lchild]
    else:
      break
    m = lchild
  arr[m] = temp


def heapsort(arr, length):
  i = int(len(arr)/2)
  while(i >= 0):
    binaryHeap(arr, len(arr), i)
    i = i - 1

  print("二叉堆的物理顺序为:")
  print(arr) # 输出二叉堆的物理顺序

  i = length-1
  while(i > 0):
    arr[i], arr[0] = arr[0], arr[i] # 变量交换
    binaryHeap(arr, i, 0)
    i = i - 1560


def pop(arr):
  first = arr.pop(0)
  return first


if __name__ == &#39;__main__&#39;:
  arr = [2, 87, 39, 49, 34, 62, 53, 6, 44, 98]

  heapsort(arr, len(arr))

  print("堆排序后的物理顺序")
  print(arr) # 输出经过堆排序之后的物理顺序

  data = pop(arr)
  print(data)

  print(arr)

Python encapsule un module de tas Nous pouvons utiliser ce module pour implémenter efficacement une file d'attente prioritaire

<.>

import heapq


class Item:
  def __init__(self, name):
    self.name = name

  def __repr__(self):
    return 'Item({!r})'.format(self.name)


class PriorityQueue:
  def __init__(self):
    self._queue = []
    self._index = 0

  def push(self, item, priority):
    heapq.heappush(self._queue, (-priority, self._index, item)) # 存入一个三元组
    self._index += 1

  def pop(self):
    return heapq.heappop(self._queue)[-1] # 逆序输出


if __name__ == '__main__':
  p = PriorityQueue()
  p.push(Item('foo'), 1)
  p.push(Item('bar'), 5)
  p.push(Item('spam'), 4)
  p.push(Item('grok'), 1)

  print(p.pop())
  print(p.pop())

Pour plus de détails, veuillez consulter le site officiel de heapq

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!