#include <iostream>
#include <ctime>
using namespace std;
#define number 20
#define maximum 200
template <typename T>
class Heap {
Heap():count(0)
{}
void insert(T data) {
tree[++count] = data;
UpHeap();
}
T extract() {
T tmp = tree[1];
tree[1] = tree[count--];
DownHeap();
return tmp;
}
void UpHeap() {
int i = count;
while (i > 1) {
if (tree[i / 2] < tree[i]) {
T tmp = tree[i / 2];
tree[i / 2] = tree[i];
tree[i] = tmp;
i /= 2;
}
else break;
}
}
void DownHeap() {
int i = 2;
while (i < count) {
if (tree[i] < tree[i+1])
i++;
if (tree[i] > tree[i / 2]) {
T tmp = tree[i / 2];
tree[i / 2] = tree[i];
tree[i] = tmp;
i *= 2;
}
else break;
}
}
void sort(int arr[], int n) {
for (int i = 0; i < n; i++) {
insert(arr[i]);
}
for (int i = 0; i < n; i++) {
arr[i] = extract();
}
}
private:
T tree[maximum];
int count;
};
int main() {
srand(time(0));
int arr[number];
for (int i = 0; i < number; i++) {
arr[i] = rand() % 50;
cout << arr[i] << " ";
}
Heap<int> Sort; //------¿¡·¯1------- Heap<int> Sort(); ¶ó°í ¾²¸é ¿¡·¯Ç®¸²
clock_t a = clock();
Sort.sort(arr, number); /* -------¿¡·¯2------ C2228 '.sort' ¿ÞÂÊ¿¡´Â Ŭ·¡½º/±¸Á¶Ã¼/°ø¿ë ±¸Á¶Ã¼°¡ ÀÖ¾î¾ß ÇÕ´Ï´Ù.
E0153, https://www.bing.com/search?q=C%2B%2B%20½Ä¿¡+Ŭ·¡½º+Çü½ÄÀÌ+ÀÖ¾î¾ß+ÇÕ´Ï´Ù. */
clock_t b = clock();
cout << "\n";
for (int i = 0; i < number; i++) cout << arr[i] << " ";
cout << "\n" << b - a << "ms\n";
return 0;
}
ÄÚµå´Â ÀÌ·¸½À´Ï´Ù...
¿¡·¯ 1À» °íÄ¡¸é ¿¡·¯2ÀÇ ³»¿ëÀÌ ³ª¿À´Âµ¥,,
¿¡·¯1Àº ¹¬½ÃÀû?¾Ï½ÃÀû?À¸·Î ()»ý¼ºÀÚ·Î µÇ¾î ¿À·ù°¡ ¾ø¾ú´ø °Í °°Àºµ¥ ¿À·ù°¡ ³ª³×¿ä.. ¿Ö³ª´Â°É±î¿ä..? //ÀÌ°Ç ±»ÀÌ ¾ÈÇØÁּŵµ µÅ¿ä. ()¾²¸é µÇ´Â°Å´Ï±î!
¿¡·¯2´Â ¿Ö³ª´Â°ÇÁö ´ëü ¸ð¸£°Ú³×¿ä.. ÅÛÇø´ÀÌ ¹®Á¦Àΰ¡? ½Í¾î¼ ´Ù Áö¿ö¼ Heap Sort;·Î µû·Î ÇØµµ ¶È°°Àº ¿À·ù°¡ ³ª¿ä.
LinkedList<int> link;
link.push_back(1);
link.push_back(2);
¸µÅ©µå ¸®½ºÆ® © ¶§µµ Àú·¸°Ô ¼±¾ðÇϰí,
Ŭ·¡½º ¸â¹öÇÔ¼ö Á¢±ÙÇÒ¶§µµ Àú·¸°Ô Á¢±ÙÇߴµ¥, ¿À·ù°¡ ¿Ö ³ª´Â°ÇÁö ¸ð¸£°Ú³×¿ä..