방송대 자료구조 교재 요약 제9 장 - 힙

제9장 힙)

 

개관)

힙은 부분적으로 정렬된 완전 이진 트리 형태다.

https://www.geeksforgeeks.org/heap-data-structure/

 

부모 노드와 자식 노드 간의 관계를 노드 값의 크기에 의해 정의한다.

노드 간의 관계에서 부모 노드가 자식 노드보다 크면 최대힙이라고 하며, 부모 노드가 자식 노드보다 작으면 최소힙이라고 한다.

힙에서 노드를 삭제하거나 삽입할 경우에는 완전 이진 트리 형태를 계속 갖추어야 한다.

복습하자.

 

완전 이진 트리!!! Complete Binary Tree!!! 리프 노드에서 왼쪽에서 오른쪽으로 정렬!!!

전 이진 트리!!! Full Binary Tree!!! 자식 노드의 수가 0 아니면 2개!!!

포화 이진 트리!!! Perfect Binary Tree!!! 모든 자식 노드가 최대 2개 꽉 꽉 차 있다!!!

...

전에도 얘기한 바 있지만 영어 번역 진짜 마음에 안 든다...

...

다시 교재 내용으로 돌아가서,

부모 노드와 자식 노드 사이의 대소관계도 계속 갖추어 주어야 한다.

즉, 힙 자료구조를 사용 시에는 노드 간의 관계와 완전 이진 트리의 정의를 만족시키며, 노드의 삭제 연산과 삽입 연산을 구현해야 한다.

...

학습 목표)

1. 힙의 정의를 이해한다.

2. 힙의 구성 방법을 이해하고, 힙의 노드 삽입 연산과 삭제 연산을 이해한다.

3. 최대힙과 최소힙을 이해한다.

...

용어 정리)

힙(heap): 부모 노드와 자식 노드 사이에 일정한 대소관계를 정의하여 구성한 완전 이진 트리이며 우선순위 큐와 같다.

최대힙: 루트가 가장 큰 값을 갖고 부모는 자식보다 큰 값을 갖는 완전 이진 트리

최소힙: 루트가 가장 작은 값을 갖고 부모는 자식보다 작은 값을 갖는 완전 이진 트리

...

1. 우선순위 큐

피라미드 모양으로 쌓아 올린 더미를 힙(heap)이라 한다.

이에 관한 이미지를 찾다가 좋은 사이트를 발견했다.

http://www.ktword.co.kr/test/view/view.php?no=6106

힙

대한민국의 레거시 사이트(?) 중 하나라고 해도 과언이 아닐 정도로 오래 된 곳인데 오랜 만에 보네...

용어나 개념 이해하고 싶으면 여기서 그냥 바로 찾으면 됨.

아무튼,

https://unsplash.com/photos/piled-stones-IiEFmIXZWSw

태초에 돌무더기가 있었으니

당신은 그 중에서 하나를 빼내야 한다.

무엇을 빼내겠는가?

개인적으로 가장 상식적이고 세상에 도움이 되는 빛과 소금 같은 사람은 '맨 위에 있는 돌을 뺀다'와 같은 답을 하는 사람이라 생각한다.

왜?

안 그러면 그동안 쌓아 놓은 돌무더기가 무너지거든.

IT는, CS는, 컴퓨터는 비효율적인 짓을 용납하지 않는다.

힙이 맨 위에 있는 데이터를 빼는 방식으로 동작하는 자료구조라는 얘기다.

 ...

힙은 무언가를 쌓아 놓은 더미고 항상 가장 위에 있는 것을 우선 꺼내는 구조를 상징한다.

그래서 최소힙이면 전체 노드에서 가장 작은 값만 뽑는 거고, 최대힙이면 전체 노드에서 가장 큰 값만 뽑는 거다.

...

그런데 힙을 제대로 이해하려면 먼저 우선순위 큐부터 알아야 한다.

...

자러 간다.

나머지 내일은 아침에.