힙 정렬 - 오름차순 및 내림차순 정렬에 사용할 힙 (최소/최대)은 무엇입니까?

Question

나는 아주 특이한 것을 눈치 채고있다.

lecture을 거친 후 C++에서 heap-sort 용 코드를 구현했습니다.

코드는 다음과 같습니다. (또는 분 힙을 구축 한 후 루트 분 - heapify을 실행하는) 오름차순으로 발생한다 분을 추출 - A 최소 힙 를 구축 -

template<typename T> void min_heapify(std::vector<T> &vec, int i, int size) 
    { 
     int left = (2*i); //left child of a zero-indexed heap (array) 
     int right = (2*i)+1; //right child. 
     int min; 

     min = ((left<size) && (vec[left] < vec[i])) ? left : i; 
     min = ((right<size) && (vec[right] < vec[min])) ? right : min; 

     if (min!= i) 
     { 
      swapper(vec[i],vec[min]); 
      min_heapify(vec, min, size); 
     } 
    } 
    template<typename T> void build_min_heap(std::vector<T> &vec, int size) 
    { 
     int i = size/2; 
     while(i--) 
     { 
      min_heapify(vec, i, size); 

     } 
    } 
    template<typename T> void heap_sort(std::vector<T> &vec, int size) 
    { 
     // build min heap 
     build_min_heap(vec, size); 
     // then extract min repeatedly. 
     while(size>0) 
     { 
      size--; 
      swapper(vec[0],vec[size]); 
      min_heapify(vec,0,size); 
     } 
    } 

    int main() 
    { 
     vector<int> v{14,-1,1000, -999, 3,2,5,10}; 
     heap_sort(v, v.size()); 

     return 0; 
    } 

특이한 점은 이 나에게 의미가 있다는 것입니다. 그러나,이 코드를 실행하고 결과 벡터를 인쇄 한 후, 내가 얻을 :

1000 14 10 5 3 2 -1 -999 

무슨 일이 일어나고 있는지 이해하려고 시도하는 동안, 나는

min = ((left<size) && (vec[left] > vec[i])) ? left : i; 
min = ((right<size) && (vec[right] > vec[min])) ? right : min; 

에

min = ((left<size) && (vec[left] < vec[i])) ? left : i; 
min = ((right<size) && (vec[right] < vec[min])) ? right : min; 

변경

실제로 더 큰 (또는 최대) 상위 노드와 하위 노드를 선택하게되고 결과 벡터는

입니다.

-999 -1 2 3 5 10 14 1000 

내가 잘못했거나 힙/힙 정렬에 대한 이해가 명확하지 않습니까? 내가 여기서 무엇을 놓치고 있니?

Answer 1

예 swapper(vec[0],vec[size]);을 추출합니다. 첫 번째 요소를 벡터의 마지막 요소로 추출합니다. 그러므로 반대 결과를 얻는다.

힙 (heaps) 최소 요소는 vec[0]입니다. 마지막 위치로 스와핑하면 해당 벡터 내에서 최대에서 최소 순서가 생성됩니다.

당신이

result.push_back(heap.pop_min()); 

뭔가를 구현하는 경우 당신은 당신이 기대했던 주문을 얻을 것이다.