Heap Tree (보기좋게출력)

Heap을 이용한 Tree 생성

 

Heap.h

#define HEAP_SIZE 15

void reheapUp(int heap[], int newNode);
void reheapDown(int heap[], int root, int last);
void buildHeap(int heap[], int size);

bool insertHeap(int heap[], int& last, int data);
bool deleteHeap(int heap[], int& heapLast, int& dataOut);
void swap(int heap[],int root,int largeChildIndex);

void reheapUp(int heap[], int newNode)
{
 int parent;
 //int hold;

 if (newNode !=0) // if(newNode)
 {
  parent=(newNode-1)/2;

  if(heap[newNode] > heap[parent])
  {
   swap(heap, newNode, parent);

   /*hold = heap[parent];
   heap[parent]=heap[newNode];
   heap[newNode] = hold;*/

   reheapUp(heap, parent);
  }
 }
 return;
}

 

void reheapDown(int heap[], int root, int last)
{
 //int hold;
 int rightKey;
 int leftKey;
 int largeChildKey, largeChildIndex;

 if((root * 2 + 1) <= last)
 {
  leftKey=heap[root * 2 + 1];

  if(root * 2 + 2<=last)
  {
   rightKey = heap[root * 2 + 2];
  }
  else
  {
   rightKey = -1; // 아주작은값!
  }
  // 자식들중에 큰 키 찾기
  
  if(leftKey>rightKey)
  {
   
   largeChildKey = leftKey;
   largeChildIndex = root * 2 + 1;
  }
  else
  {
   largeChildKey = rightKey;
   largeChildIndex = root * 2 + 2;
  }

  if(heap[root]< largeChildKey)
  {
   swap(heap, root, largeChildIndex);

   /*int hold = heap[root];
   heap[root]=heap[largeChildIndex];
   heap[largeChildIndex] = hold;*/
   
   reheapDown(heap, largeChildIndex, last);
  }
 }
 return;
}

void swap(int heap[],int newNodeRoot,int parentLargeChildIndex)
{
 int hold = heap[newNodeRoot];
 heap[newNodeRoot]=heap[parentLargeChildIndex];
 heap[parentLargeChildIndex] = hold;
}

bool insertHeap(int heap[], int& last, int data)
{
 

 if(last == HEAP_SIZE -1)
 {return false;}

 ++last;
 heap[last]=data;
 reheapUp(heap, last);

 return true;
}
bool deleteHeap(int heap[], int& last, int& dataOut)
{
 
 if(last<0)
 {
  return false;
 }
 
 dataOut = heap[0];
 heap[0]=heap[last];
 last--;
 reheapDown(heap, 0, last);
 return true;
}

 

main.cpp

#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <ctype.h>

#define HEAP_SIZE 15
#include "Heap.h"

using namespace std;

char getAction(void);
void printHeap (int heap[], int root, int heapLast, int level);

int main(void)
{
 int heap[HEAP_SIZE];

 int data;
 int heapLast;
 int bldLooper;
 int bldIndex;
 int result;

 char action;

 cout << "힙 검증 시작"<<"\n";

 heapLast = HEAP_SIZE / 2 - 1;
 bldIndex = -1;

 cout << "heapLast: "<<heapLast << endl;
 for(bldLooper = 0;
  bldLooper <= heapLast;
  bldLooper++)
 {
  data = rand() % 999 + 1;
  insertHeap(heap, bldIndex, data);
  cout <<"data: "<<data<<endl;
 }
  
 cout<<"\n 힙 생성 완료 \n\n";

 do{
  action=getAction();

 switch(action)
 {
 case 'I':
  cout << "정수 한개를 넣으시오: ";
  cin>>data;

  result=insertHeap(heap,heapLast, data);

  if(result)
  {
   cout<<data<<" 삽입됨.\n";
  }
  else
  {
   cout<<" 힙 넘침\a\n";
  }
  break;
 case 'D' :
  result=deleteHeap(heap,heapLast, data);
  if(result)
  {
   cout<<data<<" 삭제됨.\n";
  }
  else
  {
   cout << "힙이 비었음. 삭제할 수 없음\a\n";
  }
  break;
 case 'P':
   printHeap(heap,0,heapLast,0);
   break;
 case 'Q':
   break;
 default :
  cout << "main에서 불가능한 오류 방생"<<endl;
  exit(100);
  break;
 
 }
 }while(action != 'Q');

 cout<< "힙 검증 끝"<<endl;

 return 0;

}

char getAction(void)
{
 char action;
 bool OK;

 do{
 
  cout<<"\n처리할 행위를 넣으시오<[P]rint, [I]nsert, [D]elete, [Q]uit>: ";
  cin>> action;
  cout<<endl;
  action = toupper(action);

  switch(action)
  {
   case 'P':
   case 'I':
   case 'D':
   case 'Q': OK = true;
        break;
   default :
       OK=false;
       cout << "<" << action << ">" << "잘못된 입력: ";
       cout << "다시 입력하세요\a\a\n" << action;
       break;
  }
  }while(!OK);
 
 return action;

}

void printHeap (int heap[], int root, int heapLast, int level)
{
 int child;
 int i;

 if(root <= heapLast)
 {
  child = (root * 2 + 1);
  printHeap(heap, child+1, heapLast, level +1);

  for(i=0; i<level; i++)
  {
   cout<< "    ";
  }

  cout << setw(4) << heap[root] << endl;
   
  printHeap(heap, child, heapLast, level+1);
 }
 return;
}