[자료구조] 힙 정렬(Heap Sort)

목차

정렬 종류
비교 기반 정렬(Comparison Based Sorts) 
- Selection Sort, Bubble Sort, Insertion Sort, Heap Sort, Merge Sort, Quick Sort
비비교 기반 정렬(Non-comparison Based Sorts)
- Counting Sort, Radix Sort, Bucket Sort

힙 정렬(Heap Sort)

개념

• 먼저 선택 정렬을 할 때, 가장 작은 값을 찾은 뒤 앞으로 이동했습니다. 이 과정을 전체 값들이 정렬이 될 때까지 반복해서 진행했습니다. 이로 인해 시간은 O(N^2)이 소요되게 되었습니다. 이를 이제 힙이라는 특별한 자료구조를 사용하게 되면 이를 개선할 수가 있습니다. 
  • 힙 : https://comdon-ai.tistory.com/182
• 선택 정렬은 가장 작은 값을 찾고 가장 앞으로 이동했습니다. 이를 반대로 구현한다면 가장 큰 값을 찾고 가장 뒤로 이동하는 것도 가능할 것입니다. 이를 이제 가장 큰 값을 찾는 과정을 heap을 이용한다면 시간을 줄일 수 있습니다.
• 힙정렬은 우선 주어진 배열을 heap배열로 만들어줍니다.(이 과정은 O(N)의 시간복잡도가 소요됩니다. O(NlogN)이 아닌 이유 힙 내용 참고하기) max heap을 이용하여 최댓값을 뽑아내면(O(1)) 제일 뒤에 있는 값과 swap을 시켜줍니다. 그러면 이제 max heap은 swap 된 최댓값을 제외하고 재정렬과정(O(logN))을 진행합니다. 이 과정을 리스트의 모든 요소에게 적용하게 되면 O(NlogN)만에 적용이 가능합니다.
• 

코드

• Heap Sort

  • # index=0(최상단)부터 아래 노드로 정렬하는 과정
    def max_heapify(heap_size, index):
        left, right = 2 * index + 1, 2 * index + 2
        largest = index
        if left < heap_size and arr[left] > arr[largest]:
            largest = left
        if right < heap_size and arr[right] > arr[largest]:
            largest = right
    
        if largest != index:
            arr[index], arr[largest] = arr[largest], arr[index]
            max_heapify(heap_size, largest)
    
    
    def heapsort(arr):
        # 자식노드가 있는 노드부터 정렬진행
        # 자식 노드는 idx*2+1, idx*2+2 / 부모노드는 (idx-1)//2
        # len(arr)-1 인덱스의 부모 노드부터 체크를 진행하면 됩니다.
        # 즉, (len(arr)-2)//2 = len(arr)//2-1 부터 체크를 진행합니다.
        for i in reversed(range(len(arr) // 2)):
            max_heapify(len(arr), i)
    
        for i in reversed(range(len(arr))):
            arr[i], arr[0] = arr[0], arr[i]
            max_heapify(i, 0)
    
    
    arr = [7, 3, 2, 5, 6, 10, 9, 8, 1]
    heapsort(arr)
    print(arr)
    
    -->
    [1, 2, 3, 5, 6, 7, 8, 9, 10]

출처

• https://leetcode.com/explore/learn/card/sorting/694/comparison-based-sorts/4436/