[C++로 쉽게 풀어쓴 자료구조] 10장 우선순위 큐 / 최대 힙 트리 삽입과 삭제, 정렬

안녕하세요 공대생 블로거 여니입니다.

오늘은 C++로 쉽게 풀어쓴 자료구조 10장 관련된 내용을 포스팅해보려고 합니다.

최대 힙 트리의 삽입, 삭제, 정렬 함수에 대해 설명해드리려고요!

 

일단 10장의 제목은 우선순위 큐입니다.

우선순위 큐는 데이터들이 우선순위를 가지고 있어 우선순위가 높은 데이터가 먼저 출력되는 자료구조입니다.

 

스택은 가장 최근에 들어온 데이터가 삭제되죠?

큐는 반대로 선입선출이니까 가장 먼저 들어온 데이터가 삭제되고요.

우선순위 큐는 가장 우선순위가 높은 데이터부터 삭제가 됩니다.

 

우선순위 큐는 배열, 연결 리스트 등 여러 가지 방법으로 구현이 가능하지만 그중에서도 가장 효율적인 구조는 힙 구조입니다!

힙이란?

힙은 완전 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조입니다.

간단히 말하자면 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 이진트리를 말합니다.

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

 

힙은 일종의 반 정렬 상태를 유지해서 삽입과 삭제 시간 복잡도는 모두 O(log 2 n)으로 배열과 연결 리스트보다는 상당히 유리한 방법입니다.

힙트리는 두 가지 종류가 존재하는데요!

1. 최대 힙

: 부모 노드의 키 값이 자식 노드보다 큰 경우

2. 최소 힙

: 부모 노드의 키 값이 자식 노드보다 작은 경우

 

 

1. 삽입 연산

 

이제 삽입 연산에 대해 알아보도록 하겠습니다.

삽입하고자 하는 노드는 힙 트리의 가장 마지막 위치에 이어서 삽입이 됩니다.

그리고 부모 노드와 비교를 해서 삽입 노드가 클 경우에는 부모 노드와 위치를 교환합니다.

계속 이 과정을 반복하는데 부모 노드가 삽입 노드보다 값이 클 경우에는 비로소 교환을 멈춥니다.

 

알고리즘과 코드를 보여드리도록 할게요!

(설명을 찬찬히 보시면 이해가 더 되실 거예요.)

 

내용출처 c++에서 쉽게 풀어쓴 자료구조 책

insert(key) 함수가 바로 삽입 함수입니다.

일단 heapsize를 +1 해줘서 새로운 노드가 들어갈 자리를 마련해줍니다.

i의 값은 증가된 heapsize의 값을 대입해주고요.

node [i]에 삽입하고자 하는 새로운 노드의 key값을 대입해줍니다.

i의 값이 1이 아니고 새로운 삽입 노드의 값이 부모 노드의 값보다 클 동안만 반복문을 실행합니다.

반복문의 내용은?

새로운 삽입 노드와 부모 노드의 위치를 교환해주고, i값에 위치 교환하기 전 부모노드의 위치 값을 대입해주는 과정입니다.

 

내용출처 c++에서 쉽게 풀어쓴 자료구조 책

 

알고리즘이랑 코드랑 별반 차이가 없어요.

만약 힙이 꽉 차 있으면 return;해주고

꽉 차 있지 않다면 i에 플러스된 size의 값을 대입해주고 위에서 말씀드린 내용과 동일합니다.

 

 

 

 

2. 삭제 함수 알고리즘

이번엔 삭제 함수 알고리즘과 코드에 대해 살펴보도록 하겠습니다.

삭제를 하는 경우에는 제일 먼저 루트 노드가 삭제됩니다.

그리고 빈 루트 노드 자리에는 힙의 마지막 노드를 가져와서 넣어줍니다.

힙의 마지막 노드를 가져와서 자식들과 값을 비교하고 더 큰 값과 교환이 일어납니다.

자식 노드들과 비교를 했을 때 자식 노드들이 다 작은 값인 경우에 교환의 과정이 끝나게 됩니다.

내용출처 c++에서 쉽게 풀어쓴 자료구조 책

알고리즘을 한번 같이 살펴보도록 하겠습니다.

루트 노드를 item변수에 넣어두고, 루트 노드에는 힙의 마지막 노드를 넣어줍니다.

힙의 마지막 노드 자리에 노드가 없으니까 힙 사이즈도 -1 해줍니다.

i값에는 2라는 값을 넣어 초기화해주고요.

i의 값이 힙 노드의 값보다 작거나 같을 경우 동안 반복문을 실행합니다.

// 만약 i의 값이 힙 사이즈보다 작고 and 왼쪽 노드 값이 오른쪽 노드값보다 큰 경우 largest값에 왼쪽노드의 인덱스값을 넣어주고 오른쪽 노드값이 클 경우에는 오른쪽 노드의 인덱스 값을 대입해줍니다.

 

// 마지막 노드가 더 큰 자식보다 값이 크면 이동 완료!

// 아니면 한 단계 아래로 이동합니다.

 

 

최대 힙 삭제 함수 코드입니다.

참고해서 봐주시면 될듯해요! 과정은 알고리즘에서 설명드린 것과 똑같습니다.

 

 

내용출처  c++에서 쉽게 풀어쓴 자료구조 책

 

 

3. 힙 정렬

힙 정렬하는 건 어렵지 않습니다.

힙을 이용해서 데이터를 정렬하는 방식인데요.

최대 힙에서는 삭제 시 가장 큰 값이 반환되는 성질을 이용하면 됩니다.

내용출처 c++에서 쉽게 풀어쓴 자료구조 책

 

여기서 포스팅을 마치도록 하겠습니다.

구독 좋아요!

(설명이 잘못된 부분이 있으면 댓글로 알려주세요! 수정할게요~)