힙과 인쇄에 추가

Question

우리는 수업 시간에 많은 정보를 얻었으며 교사는 우리에게 거의 가르쳐주지 못했습니다. 메모 (이 작업을 완료하기 위해 제공된 모든 것)에 따라 힙을 만들어야합니다. 그러나 내 문제는 힙에 데이터를 추가 할 방법이 없거나 주 데이터에 무엇이 들어갈 지 모른다는 것입니다. 전에 힙을 사용 해 본 적이 없으므로이 주제에 대해 아주 새로운 것입니다. 어떤 충고라도 감사 할 것입니다! 당신이 클래스 Heap의 인스턴스를 만들 필요가 main()에서

#include <iostream> 

using namespace std; 

template<class ItemType> 
class Heap{ 
    public: 
    void ReheapDown(int root,int bottom); 
    void ReheapUp(int root, int bottom); 
    void swap(ItemType * a, ItemType * b); 

    ItemType * elements; 
    int numEle; 

}; 
template<class ItemType> 
void Heap<ItemType>::swap(ItemType *a, ItemType *b) 
{ 
    ItemType x; 
    x = *a; 
    *a = *b; 
    *b = x; 
} 

template<class ItemType> 
void Heap<ItemType>::ReheapDown(int root, int bottom) 
{ 
    int maxChild; 
    int rightChild; 
    int leftChild; 

    leftChild = root*2 + 1; 
    rightChild = root*2 +2; 

    if(leftChild <= bottom) 
    { 
     if(leftChild == bottom) 
      maxChild = leftChild; 
     else 
     { 
      if(elements[leftChild] <= elements[rightChild]) 
       maxChild = rightChild; 
      else 
       maxChild = leftChild; 
     } 
     if(elements[root] < elements[maxChild]) 
     { 
      swap(elements[root],elements[maxChild]); 
      ReheapDown(maxChild,bottom); 
     } 
    } 
} 


template<class ItemType> 
void Heap<ItemType>::ReheapUp(int root, int bottom) 
{ 
    int parent; 
    if(bottom > root) 
    { 
     parent = (bottom -1)/2; 
     if(elements[parent] < elements[bottom]) 
     { 
      swap(elements[parent],elements[bottom]); 
      ReheapUp(root,parent); 
     } 
    } 
} 


int main() 
{ 


} 

Answer 1

는, 다음의 데이터 멤버의 값을 설정하고, 그 멤버 함수를 호출하여 힙을 구축 : BTW
, 코드 경우에 문제가있을 swap을 호출하면 실제 매개 변수 앞에 주소 연산자 (&)를 추가해야합니다.

int main() 
{ 
    Heap<int> heap; 
    int array[] = {1,2,3,4,5,6,7}; 
    heap.elements = array; 
    heap.numEle = sizeof array/sizeof(int); 

    int start; 
    for (start = (heap.numEle-2)/2; start >=0; start--) { 
     heap.ReheapDown(start, heap.numEle - 1); // this is the Button-Up version of heapify 
    } 

    for(int i = 0; i < heap.numEle; ++i) 
    { 
     printf("%d ", heap.elements[i]); 
    } 

    // test the Top-down version of heapify. 
    heap.elements = array; 

    int end; 
    for(end = 1; end < heap.numEle; ++end) 
     heap.ReheapUp(0, end); // this is the Top-down version of heapify 

    printf("\n"); 
    for(int i = 0; i < heap.numEle; ++i) 
    { 
     printf("%d ", heap.elements[i]); 
    } 
}