버그가있는 힙 정렬

Question

다음은 힙 정렬에서 페이지 152 이후의 CLRS에 표시된 것과 유사하다고 가정합니다.

A = [9, 0, 5, 7, 4, 6, 3, 8, 1, 2]을 입력으로 전달하면. BuildMaxHeap의 출력은 [9, 8, 6, 7, 4, 5, 3, 0, 1, 2]입니다. 어느 것이 옳은지. 그러나 HeapSort에 동일한 입력을 전달하면 나에게 [9, 8, 4, 7, 2, 3, 5, 6, 1, 0]이 표시됩니다.

누구나 내가 잘못하고있는 것에 대해 약간의 분열을 피할 수 있습니까?

def left(i): 
    return 2 * i 

def right(i): 
    return 2 * i + 1 

def HeapSize(A): 
    return len(A) - 1 

def MaxHeapify(A, i): 
    l = left(i) 
    r = right(i) 
    if l <= HeapSize(A) and A[l] > A[i]: 
      largest = l 
    else: 
      largest = i 
    if r <= HeapSize(A) and A[r] > A[largest]: 
      largest = r 
    if largest != i: 
      A[i], A[largest] = A[largest], A[i] 
      MaxHeapify(A, largest) 

def BuildMaxHeap(A): 
    for i in range(HeapSize(A) // 2, 0, -1): 
      MaxHeapify(A, i) 

def HeapSort(A): 
    BuildMaxHeap(A) 
    for i in range(HeapSize(A), 1, -1): 
      A[i], A[1] = A[1], A[i] 
      MaxHeapify(A, 1) 

Answer 1

내가 보았 듯이, 원래의 코드에 약간의 수정 (주석을 확인) :

def left(i): 
    return 2 * i + 1 

def right(i): 
    return 2 * i + 2 

def parent(i):  # your 'left' and 'right' function is good practice, keep it 
    return (i - 1) // 2 

def MaxHeapify(A, heap_size, i): 
    l = left(i) 
    r = right(i) 
    if l <= heap_size and A[l] > A[i]: 
     largest = l 
    else: 
     largest = i 
    if r <= heap_size and A[r] > A[largest]: 
     largest = r 
    if largest != i: 
     A[i], A[largest] = A[largest], A[i] 
     MaxHeapify(A, heap_size, largest)  # important: don't always sort the whole array (size of heap keeps decreasing in 'HeapSort') 

def BuildMaxHeap(A): 
    heap_size = len(A) - 1 # index of last element of the heap 
    for i in range(parent(heap_size), -1, -1): # don't miss i=0 iteration 
     MaxHeapify(A, heap_size, i) 

def HeapSort(A): 
    BuildMaxHeap(A) 
    heap_size = len(A) - 1 
    for i in range(heap_size, 0, -1): # ends at i=1. You don't swap A[0] with A[0], right? 
     A[i], A[0] = A[0], A[i] 
     MaxHeapify(A, i-1, 0)  # careful here: MaxHeapify which part of the array 

출력 : 그런 다음 아래

def left(i): 
    return 2 * i  # this is 1-based tree. Since your first element is stored in 0th cell, here is an error 

def right(i): 
    return 2 * i + 1 # same, this's 1-based 

def HeapSize(A): 
    return len(A) - 1 

def MaxHeapify(A, i): 
    l = left(i) 
    r = right(i) 
    if l <= HeapSize(A) and A[l] > A[i]: 
      largest = l  # always keep 4 white space (or tab) as indent in Python, don't mix up 
    else: 
      largest = i 
    if r <= HeapSize(A) and A[r] > A[largest]: 
      largest = r 
    if largest != i: 
      A[i], A[largest] = A[largest], A[i] 
      MaxHeapify(A, largest) 

def BuildMaxHeap(A): 
    for i in range(HeapSize(A) // 2, 0, -1):  # the last non-leaf element is (HeapSize(A)-1) // 2 
      MaxHeapify(A, i) 

def HeapSort(A): 
    BuildMaxHeap(A) 
    for i in range(HeapSize(A), 1, -1): # e.g. range(3,1,-1) gives you [3,2], you miss the 1st element 
      A[i], A[1] = A[1], A[i]  # swap with A[0], unless you don't use the 0th element of array 
      MaxHeapify(A, 1)  # here is essential error for the algorithm. Since you're doing in-place sorting, you'd not swap the largest element to end of heap then MaxHeapify the WHOLE ARRAY again. I.e. you have to MaxHeapify the heap EXCLUDING the last element 

은 당신의 코드를 기반으로 작동하는 버전입니다 테스트 :

>>> a = [9, 0, 5, 7, 4, 6, 3, 8, 1, 2] 
>>> BuildMaxHeap(a) 
>>> a 
[9, 8, 6, 7, 4, 5, 3, 0, 1, 2] 
>>> HeapSort(a) 
>>> a 
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]