[C언어] 자료구조 - 우선순위 큐 heap 힙 -2

오늘은 우선순위 큐 구현방법 중에서 가장 효율적이라는 힙에 대해서 공부하도록 합시다

 

 

힙은 영어로 heap인데 뜻이 쌓다, 더미 이런 뜻을 가지고 있고, 완전이진트리를 기반으로 합니다.

완전이진트리에 대해 복습하자면 얘는 마지막 레벨 빼고는 모두 포화인 트리라고 말했죠??

 

 

아무튼 힙에는 2가지 종류가 있는데 최대힙이랑 최소힙이 있지

max heap, min heap 영어로 이렇게 쓴다고 하더라

 

 

??? 최대, 최소하니까 뭔가 크기를 가지고 있나보구나 생각이 들지?

아 그럼 그 크기가 우선순위가 되어야 힙으로 우선순위 큐를 구현할 것 같다... 라는 생각이 들면 굿

 

 

 

Max Heap이란

○부모 노드의 키값이 자식 노드의 키값보다 크거나 같은 완전
이진 트리  key(부모노드) ≥key(자식노드)

 

 

 

 

 

Min Heap이란 

○부모 노드의 키값이 자식 노드의 키값보다 작거나 같은 완전
이진 트리  key(부모노드) ≤key(자식노드)

 

 

 

 

 

 

 

우선 얘네들도 어느정도 크기별로 정렬되어있다는 것은 알겠지??  완전히말고 어느정도 ㅎ

 

 

 

근데 앞에서 트리를 배웠잖아?? 트리는 구현할 때 배열, 연결리스트 2가지가 있다고 배웠지??

여기서는 연결리스트보단 배열로 Heap을 구현할거야

왜냐면 완전이진트리의 경우에는 배열이 더 좋다고 말했었잖아

 

 

 

그리고 0번 인덱스는 안 쓴다고도 말했지? 왜냐면 배열의 번호랑 개수랑 맞추려고 ㅎㅎ

그래야 배열일 때 특정노드의 인덱스만 알면 부모나 자식 인덱스를 계산할 수 있다고 했잖아.

 

 

 

설마 까먹은건..?

–왼쪽 자식의 인덱스 = (부모의 인덱스)*2

–오른쪽 자식의 인덱스 = (부모의 인덱스)*2 + 1

–부모의 인덱스 = (자식의 인덱스)/2

 

 힙에 대해서 정말 기본적인 것을 알고 갔는데

이제 다음 글에서는 코드와 같이 기본연산을 알아보자? 

트리랑 비슷해 그래서 대충하는 그런 감도 없지 않아... 없지 ㅋㅋㅋ 코드랑 같이 이해해보자