C++ 데이터 구조 힙

내 프로그램에 힙을 구현하려고했습니다. 힙은 이진 트리와 같습니다. 최소 힙과 최대 힙과 같은 모든 힙이이 경우입니까?이 작업은 트리에서 최대/최소 노드를 맨 위에 놓는 것입니다.C++ 데이터 구조 힙

또한 1 차원 배열을 사용하면 완전한 이진 트리가있는 경우에만 유용하다는 것을 알았습니다. 완전한 이진 트리가 없다면, 친구 클래스 인 클래스를 다른 클래스에 사용하는 것이 더 유리할 것입니다. 왜 그런가요? 예 :

template<class T> class BT; // forward declartion -> added at edit 

template<class T> 
class BTNode{ 
    friend class BT<T>; // not sure why we need two classes 
private: 
    T data; 
    BTNode<T> *leftChild; // what is the benefit of making a object Node? 
    BTNode<T> *rightChild; 
}; 

template<class T> 
class BT{ 
private: 
    BTNode<T> *root; // what is the benefit of having this root in another class? 
};

감사합니다.

출처

2012-11-17 Chris

이것은'std :: priority_queue'와 같은 컨테이너에서 사용되는 것으로, ** heap **이라고합니다. – Aesthete

@Aesthete : nit-picking, 알아. '힙 (heap) '은 구체적인 데이터 구조입니다. '우선 순위 큐 (priority queue)'는 힙 (heap)으로 구현 될 수있는 추상 데이터 유형 (즉, 인터페이스)뿐만 아니라 다른 방식으로도 구현 될 수있다. 'std :: priority_queue'는 컨테이너가 아닌 컨테이너 어댑터입니다. – rici

이것은 기본 구현이며 의미 론적 단정 짓기는 이미 제거 된 이전 주석에 대한 것입니다. – Aesthete

표준 라이브러리에는 완벽하게 좋은 힙 구현이 있습니다. 당신은 그것을 봐야만한다. (자신 만의 글을 쓸 수있는 유용한 학습 연습이다.)

바이너리 힙은 이진 트리이지만 효율적으로 벡터로 저장된다. 링크는 암시 적입니다. 다시 말하면, 위치가 i (제로 기준) 인 노드의 자식은 2i+1 및 2i+2입니다. (힙의 하나의 노드에는 하나의 자식 만 있습니다.) 즉, 링크를 실제로 저장할 필요가 없다는 것을 의미합니다. 따라서 정수와 같은 작은 데이터 객체의 경우, 필요한 공간.

Wikipedia에는 이진 힙 (일반적으로 벡터에 저장하는 종류)에 대한 멋진 기사가 있지만 다른 유형의 기사는 heaps입니다.

출처

2012-11-17 03:19:02 rici

예,'std :: make_heap (beg, end);'여기서 beg와 end는'std :: vector :: iterator' 타입입니다. – Aesthete

STL 라이브러리를 살펴 보겠습니다. STL 라이브러리를 사용하여 최소 힙을 구현해야하기 때문에 시작하는 것이 좋습니다. – Chris

C++ 데이터 구조 힙

답변

관련 문제