[DATASTRUCTURE] Heap Sort

Heap Sort 개념 : http://priv.tistory.com/61

sort.h

#pragma once #include <iostream> #include <fstream> using namespace std; #define LEFT_CHILD(x) (2*x + 1) #define RIGHT_CHILD(x) (2*x + 2) #define PARENT(x) ((x-1)/2) #define HEAP_FLAG_ON 1 #define HEAP_FLAG_OFF 0 #define LEFT_CHILD_FLAG_OFF 0 #define LEFT_CHILD_FLAG_ON 1 #define RIGHT_CHILD_FLAG_OFF 0 #define RIGHT_CHILD_FLAG_ON 1 #define HEAP_TREE_COUNT 200 #define NO_DATA -1 #define ROOT_INDEX 0 int Heap_Flag = HEAP_FLAG_OFF; int Insert_Index = NO_DATA; int Heap_Sort_Tree[HEAP_TREE_COUNT]; int Square(int Data); void Show_Heap_Sort_Tree(); void Command(); void Switch(int Index_1, int Index_2); void Initialize(); void Insert(int Data); void Up_Heap(int Parent_Index, int Present_Index); void Delete(); int Down_Heap(int Present_Index); void Instuct();

function.h

#pragma once #include "sort.h" int Square(int Data) { int result = 1; for (int i = 0; i < Data; i++) result *= 2; return result; } void Show_Heap_Sort_Tree() { int Square_Count = 0, Tree_Count = 0; for (int i = 0; i < HEAP_TREE_COUNT; i++) { cout << Heap_Sort_Tree[i] << " "; Tree_Count++; if (Tree_Count == Square(Square_Count)) { Square_Count++; Tree_Count = 0; cout << "\n"; } } } /****Instruct Function****/ // File open and Make Tree void Instuct() { ifstream fcin_input; fcin_input. open("input.txt"); int Data; while (!fcin_input.eof()) { fcin_input >> Data; Insert(Data); } } /****Command Function****/ // Get Commandation from User void Command() { int Command = 0; Initialize(); Instuct(); while (1) { cout << "1. 삽입 2. Show_Min_Heap_Sort 3. Show_Tree \n"; cin >> Command; switch (Command) { case 1: int Data; cout << "Data를 입력해주세요. \n"; cin >> Data; Insert(Data); Show_Heap_Sort_Tree(); system("pause"); system("cls"); break; case 2: Heap_Flag = HEAP_FLAG_OFF; Delete(); system("pause"); system("cls"); break; case 3: Show_Heap_Sort_Tree(); system("pause"); system("cls"); break; } } } /****Switch Function****/ void Switch(int Index_1, int Index_2) { int Data = Heap_Sort_Tree[Index_2]; Heap_Sort_Tree[Index_2] = Heap_Sort_Tree[Index_1]; Heap_Sort_Tree[Index_1] = Data; } /****Initialize Function****/ // Initialize Array (Heap_Tree) void Initialize() { for (int i = 0; i < HEAP_TREE_COUNT; i++) { Heap_Sort_Tree[i] = NO_DATA; } } /****Insert Function****/ // Insert Array (Heap_Tree) // Get Data void Insert(int Data) { if (Heap_Flag == HEAP_FLAG_OFF) { Heap_Sort_Tree[ROOT_INDEX] = Data; Heap_Flag = HEAP_FLAG_ON; Insert_Index++; } else { Insert_Index++; Heap_Sort_Tree[Insert_Index] = Data; Up_Heap(PARENT(Insert_Index), Insert_Index); } } void Up_Heap(int Parent_Index, int Present_Index) { if (Heap_Sort_Tree[Parent_Index] > Heap_Sort_Tree[Present_Index]) { Switch(Parent_Index, Present_Index); if (PARENT(Present_Index) != ROOT_INDEX) { Present_Index = PARENT(Present_Index); Up_Heap(PARENT(Present_Index), Present_Index); } } } void Delete() { if (Heap_Sort_Tree[ROOT_INDEX] > NO_DATA) { cout << Heap_Sort_Tree[ROOT_INDEX] << " "; Heap_Sort_Tree[ROOT_INDEX] = Heap_Sort_Tree[Insert_Index]; Heap_Sort_Tree[Insert_Index] = NO_DATA; Insert_Index--; Down_Heap(ROOT_INDEX); Delete(); } } int Down_Heap(int Present_Index) { if (Heap_Sort_Tree[Present_Index]>NO_DATA) { int Left_Child_Flag = LEFT_CHILD_FLAG_OFF; int Right_Child_Flag = RIGHT_CHILD_FLAG_OFF; if (Heap_Sort_Tree[LEFT_CHILD(Present_Index)] > NO_DATA) { if (Heap_Sort_Tree[LEFT_CHILD(Present_Index)] < Heap_Sort_Tree[Present_Index]) Left_Child_Flag = LEFT_CHILD_FLAG_ON; } if (Heap_Sort_Tree[RIGHT_CHILD(Present_Index)] > NO_DATA) { if (Heap_Sort_Tree[RIGHT_CHILD(Present_Index)] < Heap_Sort_Tree[Present_Index]) Right_Child_Flag = RIGHT_CHILD_FLAG_ON; } if (Left_Child_Flag == LEFT_CHILD_FLAG_ON && Right_Child_Flag == RIGHT_CHILD_FLAG_ON) { if (Heap_Sort_Tree[RIGHT_CHILD(Present_Index)] < Heap_Sort_Tree[LEFT_CHILD(Present_Index)]) { Switch(RIGHT_CHILD(Present_Index), Present_Index); return Down_Heap(RIGHT_CHILD(Present_Index)); } else { Switch(LEFT_CHILD(Present_Index), Present_Index); return Down_Heap(LEFT_CHILD(Present_Index)); } } if (Left_Child_Flag == LEFT_CHILD_FLAG_ON) { Switch(LEFT_CHILD(Present_Index), Present_Index); return Down_Heap(LEFT_CHILD(Present_Index)); } if (Right_Child_Flag == RIGHT_CHILD_FLAG_ON) { Switch(RIGHT_CHILD(Present_Index), Present_Index); return Down_Heap(RIGHT_CHILD(Present_Index)); } } }

Heap_Sort.cpp

#include "function.h" int main() { Command(); }