[자료구조] 힙(Heap)과 완전 이진 트리(Complete binary tree) 개념 및 구현

[자료구조] 힙(Heap)과 완전 이진 트리(Complete binary tree) 개념 및 구현

목차

1. 힙

2. 완전 이진 트리

3. 힙 구현

 

 

힙(Heap)

특징

1. 완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.

(*우선순위 큐: 데이터들이 우선순위를 가지고 있어, 우선순위가 높은 데이터가 먼저 나감.)

 

2. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.

힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다

-큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도

 

3. 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진트리를 말한다

힙 트리에서는 중복된 값을 허용한다 ( 이진 탐색 트리에서는 중복된 값을 허용하지 않는다 )

 

 

 

종류

최대힙 최소힙

 

최대 힙

1. 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리

2. KEY( 부모 노드 ) >= KEY( 자식 노드 )

 

최소 힙

1. 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리

2. KEY(부모 노드) <= KEY( 자식 노드 )

 

부모 노드와 자식 노드의 관계

왼쪽 자식 index = (부모 index) * 2

오른쪽 자식 index = (부모 index) * 2 + 1

부모 index = (자식 index) / 2

 

 

 

시간복잡도

삽입:O(logn)

1. 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 삽입

2. 새로운 노드를 부모 노드들과 교환

 

삭제:O(logn)

1. 최대 힙에서 최대값은 루트 노드이므로 루트 노드가 삭제됨(최대 힙에서 삭제 연산은 최대 값의 요소를 삭제하는 것이다.)

2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.

3.힙을 재구성한다.

 

 

 

완전 이진 트리(Complete binary tree)

배경 지식

-이진 트리의 구조(참고)

이진 트리 구조

 

정의

정의

 

부모노드에서 시작해, 좌측에서부터 채워져 있는 구조의 이진 트리를 의미한다.

 

 

 

최대 힙 구현

 

#include <iostream>
#include <string.h>
using namespace std;
// index 1부터 힙시작
int heap[256];
int heap_count = 0;

void swap(int* a, int* b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void push(int x) {
	cout << "push: " << x << endl;
	// 1. 마지막 자리에 값을 넣는다.
	heap[++heap_count] = x;

	// 2. 자리를 지정한다.
	int child = heap_count;
	int parent = child / 2;

	while (child > 1 && heap[child] > heap[parent]) {
		swap(&heap[child], &heap[parent]);

		// check 위치 초기화
		child = parent;
		parent = child / 2;
	}
}

void pop() {
	// 최대힙
	int result = heap[1];
	cout << "pop: " << result << endl;
	swap(&heap[1], &heap[heap_count]);

	// 힙 초기화
	heap[heap_count--] = 0;
	
	
	int parent = 1;
	int child = 2;

	// 큰 놈과 비교
	if (child + 1 <= heap_count) {
		if (heap[child] <= heap[child + 1]) {
			child = child + 1;
		}
	}

	while (child > 1 && heap[child] > heap[parent]) {
		swap(&heap[child], &heap[parent]);

		// check 위치 초기화
		parent = child;
		child = parent / 2;

		// 큰 놈과 비교
		if (child + 1 <= heap_count) {
			if (heap[child] <= heap[child + 1]) {
				child = child + 1;
			}
		}
	}
	
}

int main() {
	push(30);
	push(25);
	push(28);
	push(40);
	pop();
	pop();
	for (int i = 1; i < 5; i++) {
		cout << heap[i] << " ";
	}
	return 0;
}