Codebeispiele für die Implementierung von binärem Heap und Heap-Sortierung in Python

Der folgende Editor zeigt Ihnen ein Beispiel für die Implementierung von binärem Heap und Heap-Sortierung in Python. Der Herausgeber findet es ziemlich gut, deshalb teile ich es jetzt mit Ihnen und gebe es als Referenz. Folgen wir dem Editor und werfen wir einen Blick darauf.

Der Heap ist eine spezielle Baumstruktur, und die Datenspeicherung im Heap erfüllt eine bestimmte Heap-Reihenfolge. Die Heap-Sortierung ist eine Auswahlsortierung, und ihre Algorithmuskomplexität und Zeitkomplexität haben große Vorteile gegenüber anderen Sortieralgorithmen.

Heaps werden in Big-Headed-Heaps und Small-Headed-Heaps unterteilt. Wie der Name schon sagt, ist das erste Element des Big-Headed-Heaps das größte. Jeder übergeordnete Knoten mit untergeordneten Knoten hat einen Datenwert, der größer ist der seiner untergeordneten Knoten. Der Wert der Punkte sollte groß sein. Xiaotou Dui ist das Gegenteil.

Ich werde kurz den Algorithmusprozess zum Aufbau eines Baumhaufens erläutern:

Suchen Sie ausgehend davon die Array-Daten an Position N/2 Position: Finden Sie den Index des linken untergeordneten Knotens des Knotens, vergleichen Sie zuerst die untergeordneten Knoten unter diesem Knoten, suchen Sie den größten, weisen Sie den Index des größten untergeordneten Knotens dem linken untergeordneten Knoten zu und weisen Sie dann den größten untergeordneten Knoten zu Der Punkt wird mit dem übergeordneten Knoten verglichen. Wenn er größer als der übergeordnete Knoten ist, werden Daten mit dem übergeordneten Knoten ausgetauscht. Natürlich habe ich nur kurz über die Implementierung gesprochen. Während dieses Prozesses müssen wir auch die Situation berücksichtigen, in der der Knoten nicht existiert.

Sehen Sie sich den Code an:

# 构建二叉堆 
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))

Der Heap-Sortierprozess besteht darin, den letzten zu sortieren Knoten nacheinander Vergleichen und Austauschen mit dem ersten Knoten:

# 构建二叉堆
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 kapselt ein Heap-Modul. Mit diesem Modul können wir effizient eine Prioritätswarteschlange implementieren

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())

Weitere Informationen finden Sie auf der offiziellen Website von heapq

Das obige ist der detaillierte Inhalt vonCodebeispiele für die Implementierung von binärem Heap und Heap-Sortierung in Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!