'heapSort'에 해당되는 글 1건

heapSort

1. IT Story/Development 2012. 4. 4. 15:51



heapSort

#include<iostream>
#include<iomanip>
#include "maxHeap.h"
using namespace std;

#define MAX_ARY 15


void heapSort(int list[], int last);

int main()
{

 int ary[MAX_ARY]={12,12,23,54,67,43,67,87,56,4,3,2,54,67,9};


 cout << "before sort"<<endl;

 for(int i=0; i<MAX_ARY; i++)
 {
  cout<<setw(3)<<ary[i];
 }

 cout<<endl;

 cout<<"after heap sort"<<endl;

 heapSort(ary, MAX_ARY-1);

 for(int i=0; i<MAX_ARY; i++)
 {
  cout<<setw(3)<<ary[i];
 }
 cout<<endl;

}

void heapSort(int list[], int last)
{
 int sorted;//index
 int hold;
 int walker;
 //heap building 하기

 for(walker=1; walker <= last; walker++)
 {
  reheapUp(list, walker);
 }
 //sort

 int pass=1;


 sorted = last;
 while(sorted >0)
 {
  hold=list[0];
  list[0] = list[sorted];
  list[sorted]=hold;
  sorted--;
  reheapDown(list, 0, sorted);

  cout<<"PASS"<<pass++<<":";
  for(int i=0; i<MAX_ARY; i++)
  {
  cout<<setw(3)<<list[i];
  }
  cout<<endl;
 }
}

 

 

#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;
}

'1. IT Story > Development' 카테고리의 다른 글

무료 IT 개발 언어공부, 코딩공부 유튜브 TOP5  (0) 2021.01.26
selectionSort  (0) 2012.04.04
shellSort  (0) 2012.04.04
오픈 API를 이용한 간단한 번역프로그램  (0) 2012.03.29
ChatClient  (0) 2012.03.29
MultiChatServer  (0) 2012.03.29
MultiChatClient  (0) 2012.03.29
큐를 이용한 간단한 구직Pro  (0) 2012.03.29
블로그 이미지

운명을바꾸는자

IT와 함께 살아가는 삶

,