CS/자료구조

[자료구조]이진 힙 (Binary Heap)

lingk 2021. 1. 12. 15:23

이진 힙 (Binary Heap)

👉 완전 이진트리를 기본으로 하는 자료구조

👉 각 노드의 값은 해당 노드의 후손 노드의 값보다 크거나 같음

👉 새로운 entry를 추가하기 위해서는, 새로운 entry를 가장 마지막 spot에 위치하고 reheapification

👉 가장 큰 entry를 삭제하기 위해서는, 가장 마지막 노드를 root에 위치하고 reheapfication

👉 배열에 트리의 값들을 넣어줄 때, 0 번째는 건너뛰고 1 번 index 부터 루트노드가 시작

(노드의 고유번호 값과 배열의 index 를 일치시켜 혼동을 줄이기 위함)

 

 

최대 힙 (max heap) 구현

🌀 왼쪽 자식 인덱스 : (부모 인덱스) * 2

🌀 오른쪽 자식 인덱스 : (부모 인덱스) * 2 + 1

🌀 부모 인덱스 : (자식 인덱스) / 2

삽입 (Insert)

void Heap::heap_insert(int data)
{
    int idx;
    int parent;
    
    heap.push_back(data);
    idx = heap.size() - 1;
    parent = idx/2;
    
    while(idx != 1 && data > heap[parent])
    {
        heap[idx] = heap[parent];
        heap[parent] = data;
        idx = parent;
        parent = idx/2;
    }
}

 

삭제 (Delete)

void Heap::heap_delete_max()
{
    int idx = 1;
    int left_child = idx * 2;
    int right_child = idx * 2 + 1;
    
    heap[idx] = heap[heap.size() - 1];
    heap.pop_back();
    
    while (right_child < heap.size() && (heap[idx] < heap[left_child] || heap[idx] < heap[right_child]))
    {
        int child;
        if (heap[idx] < heap[left_child])
            child = left_child;
        else child = right_child;
        
        swap(heap[idx], heap[child]);
        idx = child;
        left_child = idx * 2;
        right_child = idx * 2 + 1;
    }
}

 

전체보기_heap.cpp

더보기
//
//  heap.cpp
//  binaryHeap
//
//  Created by 최세린 on 2021/01/12.
//

#include "heap.hpp"

void Heap::heap_insert(int data)
{
    int idx;
    int parent;
    
    heap.push_back(data);
    idx = heap.size() - 1;
    parent = idx/2;
    
    while(idx != 1 && data > heap[parent])
    {
        heap[idx] = heap[parent];
        heap[parent] = data;
        idx = parent;
        parent = idx/2;
    }
}

void Heap::heap_delete_max()
{
    int idx = 1;
    int left_child = idx * 2;
    int right_child = idx * 2 + 1;
    
    heap[idx] = heap[heap.size() - 1];
    heap.pop_back();
    
    while (right_child < heap.size() && (heap[idx] < heap[left_child] || heap[idx] < heap[right_child]))
    {
        int child;
        if (heap[idx] < heap[left_child])
            child = left_child;
        else child = right_child;
        
        swap(heap[idx], heap[child]);
        idx = child;
        left_child = idx * 2;
        right_child = idx * 2 + 1;
    }
}

void Heap::heap_print()
{
    for(int i = 1; i < heap.size(); i++)
        cout << heap[i] << endl;
    
}

void Heap::swap(int &num1, int &num2)
{
    int tmp;
    tmp = num1;
    num1 = num2;
    num2 = tmp;
}

전체보기_main.cpp

더보기
//
//  main.cpp
//  binaryHeap
//
//  Created by 최세린 on 2021/01/12.
//

#include <iostream>
#include <vector>
#include "heap.hpp"

using namespace std;


int main(int argc, const char * argv[]) {
    
    Heap heap = Heap();
    
    heap.heap_insert(1);
    heap.heap_insert(2);
    heap.heap_insert(20);
    heap.heap_insert(16);
    heap.heap_insert(22);
    
    heap.heap_print();
    
    cout<<endl;
    
    heap.heap_delete_max();
    heap.heap_print();
    return 0;
}

실행결과

 

heap_insert 과정


힙 정렬 (heap sort)

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

 

✔️ 장점

가장 큰 값 몇 개만 필요할 때 힙정렬 알고리즘이 유용

 

✔️ 시간복잡도

힙에 자료를 하나 넣을 때 평균 O(logn)의 복잡도를 가지며, 이를 n번 반복하기 때문에 전체 복잡도는 O(nlogn)

 

 

gusdnd852.tistory.com/129
반응형