Lecture 4: Heaps and Heap Sort

Priority Queue ( 우선순위 큐)

컴퓨터 과학에서, 우선순위 큐는 평범한 큐나 스택과 비슷한 축약 자료형이다. 그러나 각 원소들은 우선순위를 갖고 있다. 우선순위 큐에서, 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. 만약 두 원소가 같은 우선순위를 갖는다면 그들은 큐에서 그들의 순서에 의해 처리된다(선입선출).

 

* 우선순위 큐가 힙이라는 것은 널리 알려진 오류이다. 우선순위 큐는 "리스트"나 "맵"과 같이 추상적인 개념이다. 마치 리스트는 연결 리스트나 배열로 구현될 수 있는 것과 같이, 우선순위 큐는 힙이나 다양한 다른 방법을 이용해 구현될 수 있다. 

 

우선순위 큐는 최소한 다음의 연산이 지원 되어야 한다:

 

- insert_with_priority: 하나의 원소를 우선순위를 지정하여 큐에 추가한다.

- pull_highest_priority_element: 가장 높은 우선순위를 가진 원소를 큐에서 제거하고 이를 반환한다.

 

 => 이것은 "pop_element(Off)", "get_maximum_element", 또는 "get_front(most)_element"라고 알려져 있기도 하다.우선순위의 순서를 뒤집어 낮은 값의 것을 높은 우선도로 생각하는 경우도 있는데, 이것은 "get_minimum_element"라고 알려져 있고, "get-min"이라고 쓰기도 한다.pull_highest_priority_element는 "peek_at_highest_priority_element"와 "delete_element" 함수로 나뉘어 정의될 수 있다.

 

이들 연산 이외에도 더 복잡한 연산을 지원하는 고급 기능들을 구현할 수도 있다. 예로 pull_lowest_priority_element라는 연산을 정의해 처음 높은 우선순위나 낮은 우선순위의 원소들을 살펴보는 기능을 만들 수도 있고, 큐를 모두 비우거나, 큐의 부분집합을 비우거나, 여러 원소들을 한번에 삽입하거나, 둘 이상의 큐를 하나로 병합하거나, 임의의 원소의 우선순위를 증가시키는 등의 연산을 정의할 수도 있다.

 

Heap (힙)

- Implementation of a priority queue (더 효율적인)

- An array, visualized as a nearly complete binary tree

- Max Heap Property: The key of a node is >= than the keys of its children 

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

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

 

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

 

키 값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는다. 

 

각 노드의 자식노드의 최대개수는 힙의 종류에 따라 다르지만, 대부분의 경우는 자식노드의 개수가 최대 2개인 이진 힙(binary heap)을 사용한다.

 

힙에서는 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 뿌리노드에 오게 되는 특징이 있으며, 이를 응용하면 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.

 

 

최대 힙 

> C 언어

void swap(int *a,int *b)
{
  int tmp;
  tmp=*a;
  *a=*b;
  *b=tmp;
}
int max(int a,int b,int c)
{
  int max=0,q;
  if(tree[a]>max) {
    max=tree[a];
    q=a;
  }
  if(tree[b]>max) {
    max=tree[b];
    q=b;
  }
  if(tree[c]>max) {
    max=tree[c];
    q=c;
  }
  return q;
}
void create_heap()
{
  end=N/2;
  for(i=end;i>=1;i--) {
    nnow=i;
    while((qq=max(nnow,nnow*2,nnow*2+1))!=nnow) {
      swap(&tree[nnow],&tree[qq]);
      nnow=qq;
    }
  }
}

최대 힙 정렬

void hsort(int a[],int n) //need to be changed.
{
   int i,temp;
   for(i=n/2-1;i>=0;i--)
      makeTreeHeap(i,n);
   for(i=n-1;i>=1;i--)
   {
      temp=a[i];a[i]=a[0];a[0]=temp;
      makeTreeHeap(1,i-1);
   }
}

 

 

Heap Sort (힙 정렬)

힙 정렬(Heap sort)이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.

 

>알고리즘

 

1. n 개의 노드에 대한 완전 이진트리를 구성한다. 이때 루트 노드부터 부모노드, 왼쪽 자식노드, 오른쪽 자식노드 순으로 구성한다.

2. 최대 힙을 구성한다. 최대 힙이란 부모노드가 자식노드보다 큰 트리를 말하는데, 단말 노드를 자식노드로 가진 부모노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어갈 수 있다.

3. 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다.

4. 2와 3을 반복한다.

 

>시간복잡도

 

이진 트리를 최대 힙으로 만들기 위하여 최대 힙으로 재구성하는 과정이 트리의 깊이 만큼 이루어지므로 O(logn)의 수행시간이 걸린다. 구성된 최대 힙으로 힙 정렬을 수행하는 데 걸리는 전체시간은 힙 구성시간과 n개의 데이터 삭제 및 재구성 시간을 포함한다. 시간 복잡도는

따따라서 힙 정렬은 일반적인 경우 O(nlogn)의 시간복잡도를 가진다. 

 

가장 작은 것부터 가장 큰 것까지 정렬하고 싶은 리스트 { 6, 5, 3, 1, 8, 7, 2, 4 }가 있다고 하면 정렬 예시는 다음과 같다.

>소스코드

C

void downheap(int cur, int k)
{
  int left, right, p;
    while(cur < k) {
      left = cur * 2 + 1;
      right = cur * 2 + 2;

      if (left >= k && right >= k) break;

      p = cur;
      if (left < k && data[p] < data[left]) {
        p = left;
      }
      if (right < k && data[p] < data[right]) {
        p = right;
      }
      if (p == cur) break;

      swap(&data[cur],&data[p]);
      cur=p;
    }
}

void heapify(int n)
{
  int i,p;
  for(i = (n-1)/2; i >= 0; i--){
    downheap(i,n);
  }
  //for(i=0;i<size;++i)printf("%d ",data[i]);
  //printf("\n");
}

void heap()
{
  int k;
  heapify(size);
  for(k = size-1; k > 0; ){
    swap(&data[0],&data[k]);
    //k--;
    downheap(0,k);
    k--;
  }
}