heapSort

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