이진 힙 (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 sort)
최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.
✔️ 장점
가장 큰 값 몇 개만 필요할 때 힙정렬 알고리즘이 유용
✔️ 시간복잡도
힙에 자료를 하나 넣을 때 평균 O(logn)의 복잡도를 가지며, 이를 n번 반복하기 때문에 전체 복잡도는 O(nlogn)
gusdnd852.tistory.com/129
반응형
'CS > 자료구조' 카테고리의 다른 글
[자료구조] 우선순위 큐 와 힙의 차이점 (0) | 2021.01.23 |
---|---|
[자료구조] map 컨테이너_C++ (0) | 2021.01.23 |
[자료구조] 트리 (Tree) (0) | 2021.01.03 |
[자료구조] queue 컨테이너_C++ (0) | 2020.12.17 |
[자료구조] stack 컨테이너_C++ (0) | 2020.12.17 |