Python에서 힙 정렬 알고리즘을 구현하는 개념 및 코드

힙 정렬 알고리즘을 이해하기 위한 전제 조건은 완전한 이진 트리와 힙 데이터 구조를 아는 것입니다. 힙 정렬 알고리즘은 배열을 완전한 이진 트리로 시각화하므로 "힙"이라고도 합니다.

힙 정렬 알고리즘의 원리

1. 최대 힙 속성에 따라 데이터 그룹에서 가장 큰 항목이 루트 노드에 저장됩니다.

2. 루트 요소를 제거하고 배열의 끝에 넣습니다. n번째 위치), 트리 항목의 마지막 요소를 빈 공간에 넣습니다.

3. 힙 크기를 1로 줄입니다.

4. 루트 요소를 다시 힙합니다

5. 목록의 모든 항목이 정렬될 때까지 프로세스를 반복합니다.

Python은 힙 정렬 알고리즘을 구현합니다

指定数组arr= 1 12 9 5 6 10

def heapify(arr, n, i):
      largest = i
      l = 2 * i + 1
      r = 2 * i + 2
  
      if l < n and arr[i] < arr[l]:
          largest = l
  
      if r < n and arr[largest] < arr[r]:
          largest = r
  
heapifying
      if largest != i:
          arr[i], arr[largest] = arr[largest], arr[i]
          heapify(arr, n, largest)
  
def heapSort(arr):
      n = len(arr)
  
      for i in range(n//2, -1, -1):
          heapify(arr, n, i)
  
      for i in range(n-1, 0, -1):
          arr[i], arr[0] = arr[0], arr[i]
  
          heapify(arr, i, 0)
  
  arr = [1, 12, 9, 5, 6, 10]
  heapSort(arr)
  n = len(arr)
  print("Sorted array is")
  for i in range(n):
      print("%d " % arr[i], end=&#x27;&#x27;)

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