/ C

자료구조 정복하기 with C++ (8)Heap 힙

자료구조 정복하기 with C++ (8)Heap 힙

직접 코딩하면서 자료구조 공부하기

개요

자료구조와 알고리즘은 프로그램을 구성하는 가장 핵심적인 요소입니다. 프로그램 개발을 집을 짓는 것에 비유한다면 흙이나 모래, 시멘트, 목재와 같은 자재들이 바로 ‘자료구조’에 해당되고, 이러한 자재들을 이용해서 집을 짓는 것이 ‘알고리즘’에 해당됩니다. 자료구조는 가장 기본적이고 중요한 부분이기 때문에 복습하는 겸해서 직접 여러가지 자료구조를 코딩하면서 공부하기로 했습니다.

Heap 힙

완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조입니다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어졌습니다. 힙은 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있는 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다. 힙 트리에서는 중복된 값을 허용합니다.

  • 최대 힙(Max Heap)
    • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
  • 최소 힙(Min Heap)
    • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리

Heap 기능

이번에는 최대 힙(Max Heap)을 구현합니다. 트리의 기능은 다음과 같습니다.

  1. 노드 삽입
  2. 노드 삭제
  3. 노드 출력

Max Heap

maxHeap.h

MaxHeap의 헤더파일

#pragma once
#include <iostream>
using namespace std;

template <class T>
class maxHeap
{
private:
    T* heap;
    int heapSize;
    int capacity;
public:
    maxHeap(int theCapacity = 10);										//힙 생성자
    void Push(const T& e);												//노드 삽입
    void ChangeSize1D(T* heap, int oldCapacity, int newCapacity);		
    void Pop();															//노드 삭제
    void Print();														//노드 출력
};

Tree.cpp

Tree 소스코드

#include "Tree.h"
#include <iostream>

using namespace std;

template <class T>
maxHeap<T>::maxHeap(int theCapacity) {
    //if (capacity < 1) throw "Capacity >= 1";
    capacity = theCapacity;
    heapSize = 0;
    heap = new T[capacity + 1];
}

template <class T>
void maxHeap<T>::Push(const T& e) {
    if (heapSize == capacity) {
        ChangeSize1D(heap, capacity, 2 * capacity);
        capacity *= 2;
    }

    int currentNode = ++heapSize;
    while (currentNode != 1 && heap[currentNode / 2] < e)
    {
        heap[currentNode] = heap[currentNode / 2];
        currentNode /= 2;
    }
    heap[currentNode] = e;
}

template <class T>
void maxHeap<T>::ChangeSize1D(T* heap, int oldCapacity, int newCapacity) {
    T* temp = new T[newCapacity + 1];
    for (int i = 1; i <= oldCapacity; i++) {
        temp[i] = heap[i];
    }
    delete[] heap;
    heap = temp;
}

template <class T>
void maxHeap<T>::Pop() {
    //if (IsEmpty()) throw "heap is empty. Cannot delete";
    heap[1].~T();
    T lastE = heap[heapSize--];
    int currentNode = 1;
    int child = 2;
    while (child <= heapSize) {
        if (child < heapSize && heap[child] < heap[child + 1]) child++;
        if (lastE >= heap[child]) break;

        heap[currentNode] = heap[child];
        currentNode = child;
        child *= 2;
    }
    heap[currentNode] = lastE;
}

template <class T>
void maxHeap<T>::Print() {
    for (int i = 1; i <= heapSize; i++) {
        cout << i << "번 : " << heap[i] << endl;
    }
}

결과

main.cpp

#include "maxHeap.h"
#include <iostream>

using namespace std;

int main() {
	maxHeap<int>* heap = new maxHeap<int>(10);
	//maxHeap Push
	heap->Push(20);
	heap->Push(15);
	heap->Push(14);
	heap->Push(10);
	heap->Push(2);
	heap->Push(7);
	heap->Print();
	
	//maxHeap Pop
	cout << endl;
	heap->Pop();
	heap->Pop();
	heap->Print();


	return 0;
}

최대 힙 자료구조를 구현했습니다. 결과가 잘 나옵니다!