도해 데이터 구조 - 이 진 더미

자체 도해 데이터 구조 (8) - 이 진 더미
================================================================================================================================
12. 이 진 더미 (Binary Heap) 는 지난 편 에서 AVL 트 리 를 실현 하 는 번 거 로 움 을 겪 었 는데 이 편 은 매우 쉬 워 보 였 다.먼저 데이터 구조 개념 인 힙 합 (Heap) 을 말 해 보 세 요. 사실 그리 대단한 것 은 아 닙 니 다. 쉽게 말 하면 질서 있 는 대기 열 일 뿐 입 니 다. 일반적인 대기 열 은 먼저 들 어가 고 먼저 나 오 는 것 이 고 이 진 로 는 최소 먼저 나 오 는 것 입 니 다.쉽 지 않 습 니까?만약 이 대열 이 수조 로 이 루어 진다 면 도전 하 는 방식 으로 처음부터 끝까지 한 번 찾 아서 가장 작은 것 을 꺼 내 면 되 지 않 겠 습 니까?좋 습 니 다. 그러나 팀 을 나 가 는 조작 은 매우 빈번 합 니 다. 매번 도전 을 한 번 해 야 합 니 다. 그러면 효과 가 낮 습 니 다. 도전 을 하 는 시간 복잡 도 는?Ο(n), 그럼 어떻게 처음부터 끝까지 fetch 한 번 에 팀 을 나 가지 않 아 도 됩 니까?이 진 더 미 는 이 문 제 를 비교적 잘 해결 할 수 있 지만, 전에 먼저 개념 을 소개 해 야 한다.완전 트 리 (Complete Tree): 아래 그림 에서 보 듯 이 n 층 깊이 가 채 워 지기 전에 n + 1 층 깊이 를 채 우지 않 고 왼쪽 에서 오른쪽으로 채 워 야 합 니 다.
완전 세 갈래 나무 한 그루 더 주세요.
이렇게 하면 무슨 좋 은 점 이 있 습 니까?좋 은 점 은 바늘 을 편리 하 게 생략 하고 간단 한 배열 로 나 무 를 표시 하 는 것 이다. 그림 과 같다.
그러면 다음 에 이 진 더 미 를 소개 합 니 다. 이 진 더 미 는 완전 이 진 트 리 입 니 다. 임의의 서브 트 리 의 좌우 노드 (있 으 면) 의 키 값 은 뿌리 노드 보다 클 것 입 니 다. 위의 그림 은 바로 이 진 더 미 입 니 다.당신 은 가장 작은 요소 가 바로 배열 의 첫 번 째 요소 라 는 것 을 알 게 되 었 을 것 입 니 다. 그러면 이 진 더미 의 이런 질서 있 는 대열 은 어떻게 대열 에 들 어 갑 니까?그림 보기:
이 두 갈래 더미 에 하나의 단원 이 들 어 가 려 면 키 가 2 라 고 가정 하면 배열 의 끝 에 이 요 소 를 넣 은 다음 에 가능 한 한 이 요 소 를 위로 옮 겨 야 합 니 다. 옮 길 수 없 을 때 까지 이런 복잡 도 를 거 쳤 습 니 다.Ο(logn) 의 조작, 이 진 더 미 는 이 진 더 미 였 습 니까?그럼 어떻게 나 가요?어렵 지 않 아 요. 그림 보기:
팀 에서 나 오 는 것 은 반드시 배열 의 첫 번 째 요소 이다. 그러면 첫 번 째 요소 의 이전 위 치 는 빈자리 가 된다. 우 리 는 이 빈 자 리 를 잎 노드 로 옮 긴 다음 에 배열 의 마지막 요 소 를 이 빈자리 에 삽입 하고 이 '빈자리' 를 가능 한 한 위로 옮 겨 야 한다.이런 조작의 복잡 도도Ο(logn)Ο(n) 많이 강 해 졌 죠?코드 를 직접 써 보 세 요. 물론 입 니 다. 저도 써 보 겠 습 니 다.

#include "stdio.h"
#define SWAP_TWO_INT(a, b) \
a^=b; b^=a; a^=b;
class CBinaryHeap
{
  public:
    CBinaryHeap(int iSize = 100);
    ~CBinaryHeap();

    //Return 0 means failed.
    int Enqueue(int iVal);
    int Dequeue(int &iVal);
    int GetMin(int &iVal);

    #ifdef _DEBUG
      void PrintQueue();
    #endif

  protected:
    int *m_pData;
    int m_iSize;
    int m_iAmount;
};

CBinaryHeap::CBinaryHeap(int iSize)
{
  m_pData = new int[iSize];
  m_iSize = iSize;
  m_iAmount = 0;
}

CBinaryHeap::~CBinaryHeap()
{
  delete[] m_pData;
}

#ifdef _DEBUG
int CBinaryHeap::Enqueue(int iVal)
{
  if(m_iAmount==m_iSize)
  return 0;

  //Put this value to the end of the array.
  m_pData[m_iAmount] = iVal;
  ++m_iAmount;

  int iIndex = m_iAmount - 1;
  while(m_pData[iIndex] < m_pData[(iIndex-1)/2])
  {
    //Swap the two value
    SWAP_TWO_INT(m_pData[iIndex], m_pData[(iIndex-1)/2])
    iIndex = (iIndex-1)/2;
  }

  return 1;
}
#endif

int CBinaryHeap::Dequeue(int &iVal)
{
  if(m_iAmount==0)
  return 0;

  iVal = m_pData[0];
  int iIndex = 0;
  while (iIndex*2