힙 정렬 알고리즘

안녕하세요, 오늘 우리는 힙 정렬 알고리즘에 대해 논의할 것입니다. 이 알고리즘을 더 잘 이해하려면 힙 데이터 구조에 익숙하지 않은 경우 이를 확인하십시오.

힙 정렬의 정의



힙 정렬: 데이터 구조를 기반으로 하는 가장 효율적인 정렬 알고리즘 중 하나입니다.

힙소트의 공간 및 시간 복잡도



힙 정렬 알고리즘의 공간 복잡도는 O(1)입니다.


베스트 케이스
평균 케이스
최악의 경우


오(n 로그 n)
오(n 로그 n)
오(n 로그 n)


힙 정렬 방식


  • 제공하는 배열을 최대 힙으로 숨김
  • 힙 크기가 1보다 큰 동안:
  • 변환 후 root는 max-heap의 최대값이다.
  • 루트를 최대 힙의 마지막 항목으로 바꿉니다.
  • 힙 크기를 줄입니다.
  • 뿌리를 아래로 기포(무더기)하십시오.


  • 파이썬에서 힙 정렬 알고리즘 구현


  • 이 코드는 Mohit Kumra에 의해 기고되었습니다.

  • 힙파이 기능




    def heapify(arr, n, i):
        largest = i # Initialize largest as root
        l = 2 * i + 1    # left = 2*i + 1
        r = 2 * i + 2    # right = 2*i + 2
    
        # See if left child of root exists and is
        # greater than root
        if l < n and arr[largest] < arr[l]:
            largest = l
    
        # See if right child of root exists and is
        # greater than root
        if r < n and arr[largest] < arr[r]:
            largest = r
    
        # Change root, if needed
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i] # swap
    
            # Heapify the root.
            heapify(arr, n, largest)
    


    힙 정렬 기능




    def heapSort(arr):
        n = len(arr)
    
        # Build a maxheap.
        for i in range(n//2 - 1, -1, -1):
            heapify(arr, n, i)
    
        # One by one extract elements
        for i in range(n-1, 0, -1):
            arr[i], arr[0] = arr[0], arr[i] # swap
            heapify(arr, i, 0)
    


    참조 및 유용한 리소스


  • https://www.geeksforgeeks.org/heap-sort/
  • 좋은 웹페이지 즐겨찾기