[자료구조] 우선순위 큐(Priority Queue) -2

 

우선순위 큐에 적당한 것은 힙으로 결정이 되었다.

 

힙은 '트리 구조'이다. 트리를 구현하는 방법에는 배열과 연결 리스트 둘 중 하나를 선택 해야 하는데..

 

앞에서 트리를 구성했을 때 연결 리스트로 구현을 하였으니 여기서도 똑같이 구현 하면 되겠지만

이와 같은 단점이 있다.

"연결 리스트를 기반으로 힙을 구현시 새로운 노드를 힙의 마지막 위치에 추가하는 것이 쉽지 않다."

해결은 가능하고 사소하지만 간단한 문제가 아니다..

배열 기반의 힙의 경우 이런 문제는 매우 간단하게 처리 된다.

그래서 '힙'같이 새로운 노드를 추가한 이후에도 완전 이진 트리를 유지해야 하는 경우

연결리스트가 아닌 배열을 기반으로 트리를 구현해야 한다.

 

배열을 기반으로 힙을 구현할 때 필요한 것은 다음과 같을 것이다.

왼쪽과 오른쪽 자식 노드의 인덱스 값을 얻는 방법과 부모 노드의 인덱스 값을 얻는 방법.

데이터의 삭제시 자식 노드의 인덱스 값이 필요하고 데이터 추가시 부모 노드의 인덱스 값이 필요하다.

왼쪽 자식 노드의 인덱스 값	부모노드의 인덱스 값 X 2
오른쪽 자식 노드의 인덱스 값	( 부모노드의 인덱스 값 X 2 )+ 1
부모 노드의 인덱스 값	자식 노드의 인덱스 값 ÷ 2

 

이를 바탕으로 힙으로 구성된 우선순위 큐를 만들어 본다면 …

 

Heap.h

#pragma once   enum eMenu {     eInsert = 1,     eDel,     ePrint,     eExit, };   static const int ARRAY_MIN = 0; static const int ARRAY_MAX = 10;   class CHeapManager { public:     CHeapManager( );     ~CHeapManager( );       int m_ReturnParent( int nGetData );    //부모 반환     int m_ReturnLeft( int nGetData );        //왼쪽 반환     int m_ReturnRight( int nGetData );        //오른쪽 반환       int m_ReturnPreference( int nGetIndex );    //좌,우 노드중 우선 순위가 높은 쪽을 반환       int m_Start( );       void m_Insert( );     void m_Delete( );     void m_Print( );   private:       static int Heap[ARRAY_MAX];       int m_nDataNumber;        //저장된 데이터 갯수   };

Heap.cpp

#include <iostream>   #include "Heap.h"   int CHeapManager::Heap[ARRAY_MAX];   CHeapManager::CHeapManager( ) {     std::cout<<"CHeapManager 생성자"<<std::endl;     m_nDataNumber = 0; }   CHeapManager::~CHeapManager( ) {         std::cout<<"CHeapManager 소멸자"<<std::endl; }   int CHeapManager::m_Start( ) {     int nChoice = 0;     while(true)     {         std::cout<<"1. 삽입, 2.삭제. 3. 출력 4. 종료"<<std::endl;         std::cin>>nChoice;         switch (nChoice)         {         case eInsert:             {                 m_Insert( );                 break;             }         case eDel:             {                 m_Delete( );                 break;             }         case ePrint:             {                 m_Print();                 break;             }         case eExit:             {                 return eExit;             }         default:             break;         }     } }   int CHeapManager::m_ReturnParent( int nGetData ) {     return ( nGetData / 2 ); }   int CHeapManager::m_ReturnLeft( int nGetData ) {     return ( nGetData * 2 ); }   int CHeapManager::m_ReturnRight( int nGetData ) {     return ( nGetData * 2 ) + 1 ; }   int CHeapManager::m_ReturnPreference( int nGetIndex ) {//우선순위 노드 반환     //완전 이진 트리 특성상 왼쪽이 오른쪽보다 작은 값이 들어간다. (왼쪽부터 채워진다)     if( m_ReturnLeft( nGetIndex ) > m_nDataNumber )     {     //왼쪽에도 존재 하지 않을 경우 자식 노드가 존재하지 않음     //자식 노드가 하나도 존재 하지 않는 노드는 단말 노드이다.         return NULL;     }     else if( m_ReturnLeft( nGetIndex ) == m_nDataNumber )     {//왼쪽하고 같을떄, 왼쪽노드만 존재         return m_ReturnLeft( nGetIndex );     }     else     {//왼쪽, 오른쪽 둘다 있을때           if( Heap[ m_ReturnLeft( nGetIndex ) ] > Heap[ m_ReturnLeft( nGetIndex ) ] )         {        //오른쪽 자식 노드 우선순위가 높을때             return m_ReturnRight( nGetIndex );         }         else         {//왼쪽 자식 노드 우선순위가 높을때             return m_ReturnLeft( nGetIndex );         }     } }   void CHeapManager::m_Insert( ) {     if( ARRAY_MAX <= m_nDataNumber )     {         std::cout<<"가득 찻습니다."<<std::endl;     }     else     {         int nIndex = m_nDataNumber+1; //배열의 0 인덱스는 비운다 그러므로 '데이터+1'         int nData;         std::cout<<"저장할 정수를 입력해 주세요"<<std::endl;         std::cin>>nData;         //정수의 숫자가 작을수록 우선순위가 높다는 가정하에 작성           while( nIndex != 1 )         {//새 노드 저장 위치가 루트 노드의 위치일때까지 while 반복,루트 노드가 아닐때 반복             //최 하위에서 부모노드와의 비교를 통해 정렬             if( Heap[ m_ReturnParent( nIndex ) ] > nData )             {//부모와의 비교시 부모보다 우선 순위가 높을때 (숫자가 작을떄)                 Heap[ nIndex ] = Heap[ m_ReturnParent( nIndex ) ];                 //부모 노드를 실제로 한단계 내려버린다.                 nIndex = m_ReturnParent( nIndex );                 //새 노드를 레벨 올린다(인덱스 값만 변경)             }             else    //그렇지 않은 경우             {                 break;                             }         }         //새 노드의 우선순위가 제일 낮거나 해당 위치를 찾았을때 대입.         Heap[ nIndex ] = nData;         ++m_nDataNumber;     } }   void CHeapManager::m_Delete( ) {     if( 0 >= m_nDataNumber )     {         std::cout<<"비어 있습니다."<<std::endl;     }     else     {         int nBestParentIndex = ARRAY_MIN+1;             //nBestParentIndex : 마지막 노드가 저장될 위치정보를 저장         int nLastNodeData = Heap[m_nDataNumber];         //마지막 노드 저장           int nChildIndex = m_ReturnPreference( nBestParentIndex );           //루트 노드의 우선순위가 높은 자식 노드를 시작으로 반복문 시작         while( nChildIndex = m_ReturnPreference( nBestParentIndex ) )         {             if( nLastNodeData <= Heap[ nChildIndex ] )             {//마지막 노드와 우선순위 비교후 마지막 노드의 우선순위가 높을시 밖으로                 break;             }             else             {//마지막 노드의 우선순위가 높을시 비교대상 노드의 위치를 위로                 Heap[ nBestParentIndex ] = Heap[ nChildIndex ];                 nBestParentIndex = nChildIndex;                 //마지막 노드가 저장될 위치를 한단계 내림             }         }           Heap[ nBestParentIndex ] = nLastNodeData;         --m_nDataNumber;     } }   void CHeapManager::m_Print() {     for( int nCount = ARRAY_MIN+1 ; nCount <= m_nDataNumber ; ++nCount )     {         std::cout<<"총 "<<m_nDataNumber<<"개 저장중"<<std::endl;         std::cout<<nCount<<"번째 : "<<Heap[nCount]<<std::endl;     } }

main.cpp

#include <iostream>   #include "Heap.h"   int main( ) {     CHeapManager Heap;       Heap.m_Start();       return 0; }

 

출력 결과