Heap, Priority Queue

https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

우선순위큐

  • 배열,연결리스트,힙 중 힙으로 구현 하는 것(lgN)이 가장 효율적

  • 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조
  • 여러 값들 중 최댓값이나 최솟값을 빠르게 찾아내도록 만들어짐
  • 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리
  • 힙 트리에서는 중복된 값을 허용 (이진 검색 트리에서는 비허용)
  • max heap – 부모노드 key >= 자식노드 key
  • min heap – 부모노드 key <= 자식노드 key

#include <iostream>
using namespace std;
#define MAX_ELE 200

struct heaptree {
    int heap[MAX_ELE];
    int heap_size;
};


void insert_max_heap(heaptree* h, int item){
    /*
    삽입
    힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
    새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.
    */
    int cur = ++(h->heap_size);
    /*cout << cur << " " << item << endl;*/

    /* 트리를 거슬러 올라가면서 부모 노드와 비교하는 과정 */
    // cur가 루트 노트(index: 1)이 아니고, 
    //삽입할 item의 값이 i의 부모 노드(index: i/2)보다 크면
    while ((cur != 1) && (item > h->heap[cur / 2])){
        // i번째 노드와 부모 노드를 교환환다.
        h->heap[cur] = h->heap[cur / 2];
        // 한 레벨 위로 올라단다.
        cur /= 2;
    }
    h->heap[cur] = item; // 새로운 노드를 삽입

}

int delete_max_heap(heaptree* h){
    int parent, child;
    int return_item, temp;

    return_item = h->heap[1]; //루트 노드 반환하기 위해 item에 할당
    temp = h->heap[(h->heap_size)--]; //마지막 노드 temp에 넣고 사이즈 줄임
    parent = 1;
    child = 2;


    while (child <= h->heap_size){
        //현재 노드의 자식 노드 중 더 큰 자식 노드를 찾는다 (좌,우 중)
        //루트 노드의 왼쪽 자식 노드 (node2) 부터 시작
        if ((child < h->heap_size) && (h->heap[child] < h->heap[child + 1])){
            child++;
        }

        //더 큰 자식 노드보다 마지막출신 노드가 크면, while문 중지
        if (temp >= h->heap[child])
            break;

        //더 큰 자식 노드보다 마지막출신 노드가 작으면, 부모 노드와 더 큰 자식 노드 교환
        h->heap[parent] = h->heap[child];
        //한 단계 아래로 이동
        parent = child;
        child *= 2;
    }

    //마지막 출신 노드를 재구성한 위치에 삽입
    h->heap[parent] = temp;

    //최댓값(기존 루트 노드 값)을 반환
    return return_item;
}



int main(){
    /*  
        힙을 저장하는 표준적인 자료구조는 배열 이다.
        구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다.
        특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
        예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다.
        힙에서의 부모 노드와 자식 노드의 관계
        왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
        오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
        부모의 인덱스 = (자식의 인덱스) / 2
    */

    heaptree heap1;
    heap1.heap_size = 0;


    insert_max_heap(&heap1, 7);
    insert_max_heap(&heap1, 2);
    insert_max_heap(&heap1, 5);
    insert_max_heap(&heap1, 6);

    cout << delete_max_heap(&heap1) << endl;
    cout << delete_max_heap(&heap1) << endl;
    cout << delete_max_heap(&heap1) << endl;
    cout << delete_max_heap(&heap1) << endl;

    return 0;
}

 

힙정렬

  • 자료구조인 힙을 이용
  • 힙 구성 후, 원소들을 다 삽입하고 하나씩 빼면서 배열의 앞에서부터 채워 넣으면 됨
  • min 힙의 경우 작은 수부터, max 힙의 경우 큰 수 부터 하나씩 나온다
  • 즉, 내림차순 정렬 – 최대힙, 오름차순 정렬 – 최소힙 사용
  • maxheap을 만들고, 오름차순이면 배열 뒤에서부터, 내림차순이면 앞에서부터 채우면 됨
  • 전체 자료를 정렬 하는 것이 아니라, 가장 큰 값 몇개만 필요할 때 매우 유용
  • 하나의 요소를 힙에 삽입/삭제 시 힙 재정비 시간이 log_{2}n 소요
  • 요소 개수가 n개 이므로 전체적으로 O(nlog_{2}n)
#include <iostream>
using namespace std;
#define MAX_ELE 200

struct heaptree {
    int heap[MAX_ELE];
    int heap_size;
};


void insert_max_heap(heaptree* h, int item){
    /*
    삽입
    힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
    새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.
    */
    int cur = ++(h->heap_size);
    /*cout << cur << " " << item << endl;*/

    /* 트리를 거슬러 올라가면서 부모 노드와 비교하는 과정 */
    // cur가 루트 노트(index: 1)이 아니고, 
    //삽입할 item의 값이 i의 부모 노드(index: i/2)보다 크면
    while ((cur != 1) && (item > h->heap[cur / 2])){
        // i번째 노드와 부모 노드를 교환환다.
        h->heap[cur] = h->heap[cur / 2];
        // 한 레벨 위로 올라단다.
        cur /= 2;
    }
    h->heap[cur] = item; // 새로운 노드를 삽입

}

int delete_max_heap(heaptree* h){
    int parent, child;
    int return_item, temp;

    return_item = h->heap[1]; //루트 노드 반환하기 위해 item에 할당
    temp = h->heap[(h->heap_size)--]; //마지막 노드 temp에 넣고 사이즈 줄임
    parent = 1;
    child = 2;


    while (child <= h->heap_size){
        //현재 노드의 자식 노드 중 더 큰 자식 노드를 찾는다 (좌,우 중)
        //루트 노드의 왼쪽 자식 노드 (node2) 부터 시작
        if ((child < h->heap_size) && (h->heap[child] < h->heap[child + 1])){
            child++;
        }

        //더 큰 자식 노드보다 마지막출신 노드가 크면, while문 중지
        if (temp >= h->heap[child])
            break;

        //더 큰 자식 노드보다 마지막출신 노드가 작으면, 부모 노드와 더 큰 자식 노드 교환
        h->heap[parent] = h->heap[child];
        //한 단계 아래로 이동
        parent = child;
        child *= 2;
    }

    //마지막 출신 노드를 재구성한 위치에 삽입
    h->heap[parent] = temp;

    //최댓값(기존 루트 노드 값)을 반환
    return return_item;
}


void heap_sort(int a[], int n){
    heaptree h1,h2;
    h1.heap_size = 0;
    h2.heap_size = 0;

    for (int i = 0; i < MAX_ELE; ++i){
        h1.heap[i] = 0;
        h2.heap[i] = 0;
    }
    for (int i = 0; i < n; ++i){
        insert_max_heap(&h1, a[i]);
        insert_max_heap(&h2, a[i]);
    }

    //오름차순
    for (int i = (n - 1); i >= 0; --i){
        a[i] = delete_max_heap(&h1);
    }
    for (int i = 0; i < n; ++i){
        cout<<a[i]<<" ";
    }
    cout << endl;


    //내림차순
    for (int i = 0; i < n; ++i){
        a[i] = delete_max_heap(&h2);
    }
    for (int i = 0; i < n; ++i){
        cout << a[i] << " ";
    }
    cout << endl;


}


int main(){
    int test[4] = { 7, 2, 5, 6 };
    heap_sort(test, 4);
    return 0;
}

 

You may also like...