힙 Heap 자료구조

힙

 

- 완전 이진 트리

 

- 최대 힙

-- 부모 노드의 값은 항상 자식 노드보다 크거나 같음

-- 루트노드 = 트리의 최댓값

 

- 최소 힙

-- 부모 노드의 값은 항상 자식 노드 보다 작거나 같음

-- 루트 노드 = 트리의 최솟 값

 

 

 

힙 

- 최대/최소를 기준으로 데이터를 찾는 연산을 빠르게 할 수 있음 -> O(1)

- 삽입 O(logN)

- 삭제 O(logN)

 

 

우선순위 큐

- 일반 큐

-- 먼저 들어온 데이터가 먼저 나가는 FIFO 데이터 구조

 

- 우선순위 큐

-- 데이터가 들어온 순서에 상관없이

-- 우선순위가 높은 데이터 순으로 처리

-- ex: 작업 스케줄링

 

힙 정령 Heap SORT

- 힙 자료구조의 특성을 이용한 정렬 방법

 

 

Heap을 배열로 표현하기

- 완전 이진 트리이기 때문에 빈 값이 없는 일차언 배열로 표현 가능

 

Heapify

- 힙의 재 구조화

- 데이터 추가, 삭제 후에도 힙의 속성을 유지 해야함

 

데이터 추가

 

데이터 삭제