과제11_힙

●교재 본문에 제공된 프로그램 10.1, 10.2, 10.3, 10.4를 이용하면 우선순위 큐를 구현할 수 있습니다.

프로그램을 본인 취향에 맞게 재구성하세요(C 스타일 코드를 C++ 스타일로 변경하는 것을 포함).

아래의 배열 A이 주어졌을 때, 이를 MaxHeap을 구성하고, 내림차순 정렬한 결과를 콘솔창에 출력하세요.

 

A : 0, 10, -3, 7, 22, 33, 39, 4, -9, -5

 

제출: 포트폴리오 주소

포트폴리오에 포함할 내용:

- 교재 본문 소스코드를 본인 스타일로 변경한 코드 전체

- 배열 A가 주어졌을 때, MaxHeap을 이용해 내림차순 정렬하는 main 함수 코드 전체

- 콘솔창 출력 결과(캡쳐)

---

#include <iostream>
#include <iomanip>
const int MAX_ELEMENT = 20;
using namespace std;
class Heapnode {
	int key;
public:
	Heapnode(int k = 0) :key(k) {}
	void setkey(int k) { key = k; }
	int getkey() { return key; }
	//void display() { printf("%4d", key); }
	void display() { cout << left << setw(4) << key; }
};
class Maxheap {
	Heapnode node[MAX_ELEMENT];//노드의 배열
	int size;//현재 힙에 저장된 노드의 수
public:
	Maxheap() :size(0) {}
	bool isempty() { return size == 0; }
	bool isfull() { return size == MAX_ELEMENT - 1; }
	Heapnode& getparent(int i) { return node[i / 2]; }//부모노드
	Heapnode& getleft(int i) { return node[2 * i]; }//왼쪽 자식노드
	Heapnode& getright(int i) { return node[2 * i + 1]; }//오른쪽 자식노드
	void insert(int key) {
		if (isfull()) return;
		int i = ++size;//증가된 힙 위치에서 시작
		while (i != 1 && key > getparent(i).getkey()) {//루트가 아니고 자식키값이 부모노드 키값보다 클때
			node[i] = getparent(i);//node[i]에 부모노드 키값을 넣는다(부모를 자식으로 삼음)
			i /= 2;//한 레벨 위로 상승
		}
		node[i].setkey(key);//최종 위치에 데이터 복사
	}
	Heapnode remove() {
		if (isempty()) { cout << "empty error!" << endl; exit(1); }
		Heapnode item = node[1];//루트 노드
		Heapnode last = node[size--];//마지막 노드
		int parent = 1;//루트노드 인덱스
		int child = 2;//루트의 왼쪽 자식 인덱스
		while (child <= size) {//힙 트리 내에서
			if (child < size//child는 더 큰 자식노드의 인덱스가 됨.
				&& getleft(parent).getkey() < getright(parent).getkey())
				child++;//오른쪽 자식이 더 크면 오른쪽으로 이동
			if (last.getkey() >= node[child].getkey()) break;//부모노드가 자식노드보다 크면 ok
			node[parent] = node[child];//자식노드보다 작으면 swap

			parent = child;//한단게 아래 레벨로 이동
			child *= 2;
		}
		node[parent] = last;//최종 위치에 마지막 노드를 저장한다.
		return item;//삭제한 루트노드를 반환
	}
	//Heapnode find() { return node[1]; }
	void display() {
		for (int i = 1,level=1; i <= size; i++) {
			if (i == level) {
				cout << "\n";
				level *= 2;
			}
			node[i].display();
		}
		cout << "\n-------------------------------";
	}
	void heapsort(int a[], int n) {
		Maxheap h;
		for (int i = 0; i < n; i++) {
			h.insert(a[i]);
		}
		for (int i = 0; i < n; i++) {
			a[i] = h.remove().getkey();
		}
	}
};
int main() {
	Maxheap heap;
	int A[10] = { 0,10,-3,7,22,33,39,4,-9,5 };
	for (int i = 0; i < 10; i++) {
		heap.insert(A[i]);
	}
	heap.display();
	cout << endl;
	heap.heapsort(A, 10);
	for (int i = 0; i < 10; i++) {
		cout << setw(3) << A[i];
	}
}

maxheap내림차순 정렬