[MaxHeap]
/*
최대힙, MaxHeap
*/
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
template <typename T>
class MaxPQ
{
public:
virtual bool IsEmpty() = 0;
virtual void Push(const T &item) = 0;
virtual void Pop() = 0;
virtual T &Top() const = 0;
};
template <typename T>
class MaxHeap :public MaxPQ<T>
{
private:
T *heap;
int capacity;
int heapSize; //원소 개수
public:
MaxHeap(int theCapacity = 10)
{
if (theCapacity < 1)
{
cout << "최대 크기는 1보다는 커야한다" << endl;
exit(1);
}
heap = new T[theCapacity];
capacity = theCapacity;
heapSize = 0;
}
bool IsEmpty()
{
return (heapSize == 0);
}
void Push(const T &item)
{
if (capacity == heapSize)
changeSize1D(heap, capacity, 2 * capacity);
capacity = 2 * capacity;
int currentNode = ++heapSize; //heap[0]이 없으므로
while (currentNode != 1 && heap[currentNode / 2] < item) //현재 노드가 루트가 아니고 부모노드보다 클 때 break
{
heap[currentNode] = heap[currentNode / 2]; //bubble sort 부모가 밑으로 내려가고
currentNode /= 2; //현재 위치를 부모 위치로
}
heap[currentNode] = item; //삽입
}
void Pop()
{
if (IsEmpty())
{
cout << "최대힙이 비어있다" << endl;
exit(1);
}
//힙 루트 삭제
heap[1].~T();
T lastE = heap[heapSize--]; //힙의 마지막 노드를 저장하고 위치 삭제
int currentNode = 1; //현재 위치를 루트
int child = 2; //루트의 왼쪽 자식으로 child를 설정
while (child <= heapSize)
{
if (child < heapSize && heap[child] < heap[child + 1])
child++; //왼쪽 오른쪽 자식 중 더 큰 자식으로 설정
if (lastE >= heap[child])
break; //lastE를 현재 노드에 저장할 수 있는가?
//저장 못할 시
heap[currentNode] = heap[child]; //자식이 부모 위치로 올라가고
currentNode = child;
child *= 2; //부모가 자식 위치로 내려간다
}
heap[currentNode] = lastE;
}
T &Top() const
{
return heap[1];
}
template <typename T>
friend ostream &operator<<(ostream &os, MaxHeap<T> m);
};
template <class T>
void changeSize1D(T *&heap, int oldSize, int newSize) //Stack의 changeSize1D 사용
{
if (newSize < 0)
{
cout << "새로운 길이는 0 이상이여야 한다" << endl;
exit(1);
}
T *temp = new T[newSize];
memcpy(temp, heap, (oldSize * sizeof(T))); //memcpy를 이용해 기존에 있던 데이터를 새로운 배열로 옮긴다
delete[]heap;
heap = temp;
}
template <typename T>
ostream &operator<<(ostream &os, MaxHeap<T> m)
{
int idx = 1;
int level = 1;
int count = 1;
int square = 1;
while (idx <= m.heapSize) //levelOrder
{
if (idx == 1 || idx % square == 0)
os << count << "층: ";
os << m.heap[idx] << " ";
if (idx == level)
{
os << endl;
level = 2 * level + 1; //각 층의 노드 수를 계산
count++; //level당 한층씩 올라간다
square *= 2;
}
idx++;
}
return os;
}
int main(void)
{
MaxHeap<int> intHeap;
srand((unsigned)time(NULL));
for (int i = 0; i < 10; i++)
{
int number = rand() % 1000 + 1;
intHeap.Push(number);
}
cout << "MaxHeap 출력" << endl << intHeap << endl;
cout << "현재 Top: " << intHeap.Top() << endl;
for (int i = 0; i < 5; i++)
{
intHeap.Pop();
}
cout << "Pop 다섯번 한 후 MaxHeap" << endl << intHeap << endl;
cout << "현재 Top: " << intHeap.Top() << endl;
return 0;
}
[MinHeap]
/*
최소힙, MinHeap
*/
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
template <typename T>
class MinPQ
{
public:
virtual bool IsEmpty() = 0;
virtual void Push(const T &item) = 0;
virtual void Pop() = 0;
virtual T &Top() const = 0;
};
template <typename T>
class MinHeap :public MinPQ<T>
{
private:
T *heap;
int capacity;
int heapSize; //원소 개수
public:
MinHeap(int theCapacity = 10)
{
if (theCapacity < 1)
{
cout << "최대 크기는 1보다는 커야한다" << endl;
exit(1);
}
heap = new T[theCapacity];
capacity = theCapacity;
heapSize = 0;
}
bool IsEmpty()
{
return (heapSize == 0);
}
void Push(const T &item)
{
if (capacity == heapSize)
changeSize1D(heap, capacity, 2 * capacity);
capacity = 2 * capacity;
int currentNode = ++heapSize; //heap[0]이 없으므로
while (currentNode != 1 && heap[currentNode / 2] > item) //현재 노드가 루트가 아니고 부모노드보다 작을 때 break
{
heap[currentNode] = heap[currentNode / 2]; //bubble sort 부모가 밑으로 내려가고
currentNode /= 2; //현재 위치를 부모 위치로
}
heap[currentNode] = item; //삽입
}
void Pop()
{
if (IsEmpty())
{
cout << "최대힙이 비어있다" << endl;
exit(1);
}
//힙 루트 삭제
heap[1].~T();
T lastE = heap[heapSize--]; //힙의 마지막 노드를 저장하고 위치 삭제
int currentNode = 1; //현재 위치를 루트
int child = 2; //루트의 왼쪽 자식으로 child를 설정
while (child <= heapSize)
{
if (child < heapSize && heap[child] > heap[child + 1])
child++; //왼쪽 오른쪽 자식 중 더 작은 자식으로 설정
if (lastE <= heap[child])
break; //lastE를 현재 노드에 저장할 수 있는가?
//저장 못할 시
heap[currentNode] = heap[child]; //자식이 부모 위치로 올라가고
currentNode = child;
child *= 2; //부모가 자식 위치로 내려간다
}
heap[currentNode] = lastE;
}
T &Top() const
{
return heap[1];
}
template <typename T>
friend ostream &operator<<(ostream &os, MinHeap<T> m);
};
template <class T>
void changeSize1D(T *&heap, int oldSize, int newSize) //Stack의 changeSize1D 사용
{
if (newSize < 0)
{
cout << "새로운 길이는 0 이상이여야 한다" << endl;
exit(1);
}
T *temp = new T[newSize];
memcpy(temp, heap, (oldSize * sizeof(T))); //memcpy를 이용해 기존에 있던 데이터를 새로운 배열로 옮긴다
delete[]heap;
heap = temp;
}
template <typename T>
ostream &operator<<(ostream &os, MinHeap<T> m)
{
int idx = 1;
int level = 1;
int count = 1;
int square = 1;
while (idx <= m.heapSize) //levelOrder
{
if (idx == 1 || idx % square == 0)
os << count << "층: ";
os << m.heap[idx] << " ";
if (idx == level)
{
os << endl;
level = 2 * level + 1; //각 층의 노드 수를 계산
count++; //level당 한층씩 올라간다
square *= 2;
}
idx++;
}
return os;
}
int main(void)
{
MinHeap<int> intHeap;
srand((unsigned)time(NULL));
for (int i = 0; i < 10; i++)
{
int number = rand() % 1000 + 1;
intHeap.Push(number);
}
cout << "MinHeap 출력" << endl << intHeap << endl;
cout << "현재 Top: " << intHeap.Top() << endl;
for (int i = 0; i < 5; i++)
{
intHeap.Pop();
}
cout << "Pop 다섯번 한 후 MinHeap" << endl << intHeap << endl;
cout << "현재 Top: " << intHeap.Top() << endl;
return 0;
}
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.