[알고리즘/자료구조] 힙 (Heap)

힙

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(Complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다.

A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다.

힙에는 두가지 종류가 있으며, 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙을 '최대 힙', 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙을 '최소 힙'이라고 부른다.

소스

#include<stdio.h>
#include<iostream>
 
using namespace std;
 
#define MAX_ELEMENT 100
 
class MaxPriorityQueue
{
public:
        int elem[MAX_ELEMENT]; //요소의 배열
        int size; //현재 요소의 개수
public:
        void init()
        {
               size = 0;
        }
 
        int getParent(int i)
        {
               return i / 2;
        }
 
        int getLeft(int i)
        {
               return i * 2;
        }
 
        int getRight(int i)
        {
               return i * 2 + 1;
        }
 
        void insert(int data) //삽입 함수
        {
               if (size == MAX_ELEMENT)
                       return;
               int i = ++size;
               while (i != 1 && data > elem[getParent(i)]) //루트가 아니고 부모노드보다 값이 크면
               {
                       elem[i] = elem[getParent(i)]; //부모를 자식노드로 끌어내리고
                       i /= 2; //한 레벨 상승
               }
               elem[i] = data;
        }
        int remove() //최대 항목 삭제 및 반환 함수
        {
               if (!size)
                       return NULL;
               int root = elem[1];
               int last = elem[size--];
               int parent = 1;
               int child = 2;
               while (child <= size)
 
               {
                       if (child < size && elem[getParent(parent)] < elem[getParent(parent)])
                              child++;
                       if (elem[last] >= elem[child])
                              break;
                       elem[parent] = elem[child];
                       parent = child;
                       child *= 2;
               }
               elem[parent] = last;
               child *= 2;
        }
 
        int find() //최대 항목 반환 함수
        {
               return elem[1];
        }
 
        void display() //우선순위 큐의 모든 항목 출력
        {
               int res = 1;
               int square = 2;
               int height = 1;
               int start = 0;
               while (res <= size)
               {
                       res *= 2;
                       height++;
               }
 
               for (int i = 1; i <= size; i++)
               {
                       if (i==1 || i == square)
                       {
                              cout << endl;
                              for (int j = start; j < height; j++)
                                      cout << "\t";
                              if(i!=1)
                                      square *= 2;
                              start++;
                       }
                       cout << elem[i];
                       for (int j = 0; j < height - start; j++)
                       {
                              if (i % 2)
                                      cout << "\t";
                              else
                                      cout << "\t";
                       }
               }
               cout << endl;
        }
};
 
void main(void)
{
        MaxPriorityQueue q;
        q.init();
        int arr[15];
        for (int i = 0; i < 15; i++)
        {
               arr[i] = rand() % 100 + 1;
               cout << arr[i] << " ";
        }
 
        cout << endl;
        cout << "우선순위 큐" << endl;
        for (int i = 0; i < 15; i++)
               q.insert(arr[i]);
 
        q.display();
}

결과화면

출처

위키피디아

https://en.wikipedia.org/wiki/Heap_(data_structure)