[Data Structure]힙(Heap)

힙(Heap)이란? 완전이진트리(Complete Binary Tree)의 일종으로 최댓값이나 최솟값을 빠르게 구하는데 최적화된 자료구조입니다.

이때 힙은 최댓값이나 최솟값을 트리의 루트 노드에 갖습니다. 전자를 최대힙(max heap), 후자를 최소힙(min heap)이라고 부릅니다.

최대힙일 경우에는 key(부모 노드) >= key(자식 노드)를 반드시 만족하고, 최소힙일 경우에는 key(부모노드) <= key(자식 노드)를 만족합니다. (좌) 최대 힙 / (우) 최소 힙 힙의 구현(C언어) Based on Array 여기서는 최대힙을 구현하겠습니다.

최소힙은 최대힙구조에 삽입하는 원소에 -를 붙여서 삽입하면 기능상 최소힙과 동일합니다. 힙은 이진트리의 일종이므로 배열 기반으로 작성할 경우 그 구조는 배열 기반의 이진트리와 동일합니다. typedef enum { false, true } bool; typedef int HData; typedef struct { HData data;...

요청 처리 중입니다...

[Data Structure]힙(Heap)

등록된 다른 글