Python에서 이진 힙 및 힙 정렬을 구현하기 위한 코드 예제

아래 편집기는 Python에서 바이너리 힙 및 힙 정렬을 구현하는 예를 제공합니다. 편집자님이 꽤 좋다고 생각하셔서 지금 공유하고 모두에게 참고용으로 드리고자 합니다. 편집기를 따라가서 살펴보겠습니다. 힙은 특별한 트리 구조입니다. 힙의 데이터 저장은 특정 힙 순서를 충족합니다. 힙 정렬은 선택 정렬이며, 알고리즘 복잡도와 시간 복잡도가 다른 정렬 알고리즘에 비해 큰 장점을 갖습니다.

힙은 큰 머리 힙과 작은 머리 힙으로 구분됩니다. 이름에서 알 수 있듯이 큰 머리 힙의 첫 번째 요소는 자식 노드가 있는 각 상위 노드의 데이터 값이 가장 큽니다. 그 자식 노드가 큽니다. Xiaotou Dui는 그 반대입니다.

트리 힙을 만드는 알고리즘 과정을 간략히 설명하겠습니다. N/2 위치의 배열 데이터를 찾고, 이 위치부터 시작하여 해당 노드의 왼쪽 자식 노드의 인덱스를 찾은 후, 먼저 비교합니다. 이 결과 점 아래의 자식 노드 중에서 가장 큰 것을 찾아 가장 큰 자식 노드의 인덱스를 왼쪽 자식 노드에 할당한 후 가장 큰 자식 노드와 부모 노드보다 큰 경우 비교합니다. 상위 노드는 데이터를 교환합니다. 물론, 구현에 대해서 간략하게 이야기 했을 뿐입니다. 이 과정에서 노드가 존재하지 않는 상황도 고려해야 합니다.

코드를 보세요:

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

힙 정렬 프로세스는 마지막 노드를 순서대로 첫 번째 노드와 비교하고 교환하는 것입니다:

# 构建二叉堆
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은 힙 모듈을 캡슐화합니다. 이 모듈은 우선순위 큐를 매우 효율적으로 구현할 수 있습니다

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

자세한 내용은 heapq 공식 웹사이트를 참조하세요

위 내용은 Python에서 이진 힙 및 힙 정렬을 구현하기 위한 코드 예제의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!