[C언어] 자료구조 - 우선순위 큐 heap 힙 기본연산 -3

이번에는 힙의 기본연산을 알아볼 시간인데요.

 

우선 트리를 만들 때 했던 것처럼 노드를 정의해야겠죠? 어차피 배열이니까 데이터를 넣는데 이제

우선순위 큐를 만들려고 하는 것이니까 우선순위도 포함되어있어야 하는데...?

어떻게 할 것인지 코드로 보면서 알아보자

 

우선 정수의 데이터를 다룬다고 치고 알아보도록 하자

 

저기 전처리기 #define은 우선순위를 정하는 것이다. 저거 없으면 그냥 트리랑 다를바가 없다.

다른 식으로도 우선순위 큐 만들기도 하던데,, 저부분은 더 공부해야할 부분인건 확실하다.

★★★★★ 까먹지 마라고 별도 붙혀놓음

 

아무튼 저렇게 하도록 하고,,? 배열로 만들거니까 배열선언은 쉬우니까 넘어가고?

 

기본연산중 하나인 삽입연산으로 ㄱㄱㄱ

우선 알고리즘부터 알아보자면

 

삽입은 힙의 가장 마지막 부분 다음 인덱스에 새로운 데이터가 들어간다.

그 다음 그 힙이 그 위치에서 힙의 성질, max heap이나 min heap의 조건에 맞는지 비교하고 부모노드와 비교하면서

제자리를 찾아간다. max heap 같은경우 부모노드보다 작거나 같으면 그곳이 제자리인 것이다.

 

 

 

완전이진트리에서 높이는 조사할 때 O(logn) 의 시간복잡도를 가지는데

힙의 삽입연산또한 O(logn)을 가진다. 그냥 그렇다고 ㅇㅇ

 

최대힙은 이렇겠지만 최소힙은 또 다르겠지?? 어느정도는 다 같아 while 부분이 좀 다르겠지 

 

이번엔 삭제연산을 알아보자

이번에도 최대힙으로 알아보자 ㅎ

 

삭제는 가장 큰 키값을 가진 노드를 삭제하는 것 이렇게 시작해

루트에서부터 단말노드까지의 경로에 있는 노드들을 교환하여 히프 성질을 만족시키는지 보면서 내려오는 거지

 

 

 

 

 

얘가 좀 설명하기 어렵다. 그림으로 쉬운데,..ㅠㅠ

 

탐색연산을 알아보려했지만 여기선 어차피 ㅋㅋㅋ 탐색을 안하면 삽입, 삭제가 못일어나지?? ㅋㅋㅋ 이 알고리즘 내에 탐색이 포함되어있는거야 

 

아무튼 기본연산은 알아봤고.. 힙은 여기까지만 하자 ㅎㅎㅎ