HW11

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

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

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

#include <iostream>
#define MAX_ELEMENT 200

class HeapNode {
    int key;
public:
    HeapNode(int k = 0) : key(k) {}
    void setKey(int k) { key = k; }
    int getKey() { return key; }
    void display() { std::cout << 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[i * 2]; }
    HeapNode& getRight(int i) { return node[i * 2 + 1]; }

    void insert(int key) {
        if (isFull()) return;
        int i = ++size;

        while (i != 1 && key > getParent(i).getKey()) {
            node[i] = getParent(i);
            i /= 2;
        }
        node[i].setKey(key);
    }

    HeapNode remove() {
        if (isEmpty()) return HeapNode();
        HeapNode item = node[1];
        HeapNode last = node[size--];
        int parent = 1;
        int child = 2;
        while (child <= size) {
            if (child < size && getLeft(parent).getKey() < getRight(parent).getKey())
                child++;
            if (last.getKey() >= node[child].getKey()) break;

            node[parent] = node[child];
            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) {
                std::cout << std::endl;
                level *= 2;
            }
            node[i].display();
        }
        std::cout << "\n----------------------";
    }
};

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

int main() {
    int A[] = { 0, 10, -3, 7, 22, 33, 39, 4, -9, -5 }; //주어진 배열 A
    int arraySize = sizeof(A) / sizeof(A[0]); //배열에 담길 갯수
    MaxHeap maxHeap; //객체 maxHeap 선언
    for (int i = 0; i < arraySize; i++) { // 객체에 배열 A를 삽입
        maxHeap.insert(A[i]); //내림차순으로 들어가게 됨
    }

    std::cout << "내림차순으로 정렬한 결과: ";
    for (int i = 0; i < arraySize; i++) { 
        HeapNode node = maxHeap.remove(); // remove함수는 최대요소를 반환하고 그 값을 삭제한다. 반환한 최대 요소를 node에 저장한다.
        std::cout << node.getKey() << " "; //노드의 key값을 출력한다.
    }
    std::cout << std::endl;

    return 0;
}

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