간단한 힙 프로그램 -이 변수는 무엇을합니까

Question

void ReheapDown(int* heap, int top, int swpIndx, int numElements) { 
    int leftChild = 2 * top + 1; 
    int rightChild = 2 * top + 2; 
    int minChild; 
    if (leftChild < numElements) { 
     // find subscript of smallest child 
     if (rightChild >= swpIndx || heap[leftChild] < heap[rightChild]) 
      minChild = leftChild; 
     else 
      minChild = rightChild; 
     // if data at top is greater than smallest 
     // child then swap and continue 
     if (heap[top] > heap[minChild]) { 
      swap(heap[top], heap[minChild]); 
      ReheapDown(heap, minChild, swpIndx, numElements); 
     } 
    } 

이것은 단순한 힙을위한 것입니다. ReheapDown은 힙의 항목을 제거하는 데 부분적으로 사용됩니다. 그래도 swpIndx은 무엇을합니까? (나는 숙제를하기 위해 알아야하는데, 힙에 특정 키를 제거하는 함수를 작성해야만한다.)

Answer 1

힙에서 키를 제거하려면, 삭제하기 전에 힙의 마지막 키를 누릅니다. 그렇지 않으면 힙에 커다란 구멍이 생깁니다. 우리는 당신이 제공하는 것과 ReheapDown 방법이 들어오는 곳이다 힙의 순서를 화나게 할 수 있습니다 제거 할 노드와 마지막 노드를 교환하지만

.

은 내가 swpIndex 매개 변수를 믿는다 제거하려는 요소를 배치 한 색인입니다. 그래서 코드의 일부는 기본적으로 말한다 :

if (there exists a left child) { 
    if (there is no right child || left child < right child) 
     minChild <- left child 
    else 
     minChild <- right child 
} 

나는 유일한 목적은 왼쪽과 오른쪽 아이의 존재를 확인하는 것입니다 있다고 보이기 때문에 매개 변수가 있지만 불필요하다고 생각; 이것은 leftChild 및 rightChild 인덱스를 numElements와 비교하여 수행 할 수도 있습니다.

호프가 도움이 되길 바랍니다.