꿈 꾸는 누렁이

내가 퀵 정렬까지 공부할 줄은 몰랐(었)다. 역시 차근차근 해 놓는게 중요하다. 더불어 포스팅도 그 때 그 때 하지 않으면 이렇게 개 고생한다.

어찌됐건 오늘은 퀵 정렬이다.

나는 이게 퀵 정렬이 겁나 빨라서 퀵 정렬인가 했는데, 맞다. 겁나 빠른 퀵 정렬 한 번 기록해둔다.

퀵 정렬이란?

퀵 정렬은 이름을 통해서는 대충 어떤 정렬인지 짐작하기가 힘들다. 뭐 병합 정렬과 같은 경우는 뭔가 병합 해나가겠지 싶었는데 퀵 정렬은 아니다. 그래서 퀵 정렬이 무엇인가 라기 보다는 퀵 정렬의 작동 원리를 기록하는게 나의 인생에, 그대의 인생에 더 유익하지 않을까 싶다.

퀵 정렬은 병합 정렬과 매우 비슷하게, 쪼개는 것이 그 기본으로 깔려 있는 정렬이다. 또 쪼개기 시작한다는거다. 쪼갠다는 것의 의미는 병합 정렬에 잘? 설명되어 있는진 모르겠고 애타게 설명을 적어 놓았다.

https://typingdog.tistory.com/122?category=924874

퀵 정렬의 주된? 사상?은 이렇다. 

1. 배열을 쪼개는 것과 동시에 정렬하는 것이 아니다
2. 그렇다고 해서 앞/뒤 비교를 하며 정렬을 한다고 생각하면 안된다.
3. 어떤 기준에 맞는 '하나'의 요소의 정렬된 위치를 찾고, 고정한 뒤, 그 위치를 중심으로 양 옆 두개로 쪼개는 것이다. 이 때, 고정된 요소는 이미 올바른 정렬 위치를 찾았으니 정렬 대상에서 제외한다.

그러니까 결국에는 주어진 범위에 한해서 어떤 기준에 의거하여 단 하나의 요소의 올바른 정렬 위치를 찾아나가고 그 위치를 기준으로 양 옆으로 쪼개는 것을 반복해나간다고 생각하면 된다.

사과해야겠다. 이게 무슨 말이냐? 그림으로 기록해야겠다.

이런 배열이 있다.

이 배열을 아주 오도방정을 떨면서 왔다갔다 할 이상한 인덱스들을 소개하겠다.

자, 그림 내에 설명을 기록했지만, 추가 설명이 필요한 부분을 기록하겠다. 

일단, pivot은 비교의 기준이라고 했는데 꼭 이 기준을 맨 왼쪽에 둘 필요도 없다. 다만 이런 기준이 어디에 있긴 있어야한다는 소리인데, 오름차순 정렬의 경우 맨 왼쪽에 많이 쓴다고 생각한다고 생각한다....ㅋㅋ

left와 right는 무조건 배열 전체 중 인덱스 0과 인덱스 끝을 나타내는게 아니라 주어진 범위 내에서 가장 왼쪽과 오른쪽을 나타내는 것이기 때문에, 물결 표시로 강조를 했다.

기본적인 동작은 다음과 같다.

low와 high가 서로를 넘어선 경우이다. 이 경우에는 더 진행해도 (row의 입장에서)pivot보다 작은 값이, (high의 입장에서)pivot보다 큰 값이 나올리가 없기 때문이다. -> 우리는 지금 pivot을 기준으로 작은 값들을 왼쪽으로 몰아왔고, 큰 값들을 오른쪽으로 몰아왔다. 눈으로 잘봐라.

그러면 이제 몰려있는 곳의 경계가 있을 것이다. 3과 6 사이이다. 그 사이에 pivot 값을 넣고 뒤에 값들을 하나씩 땡기고 할 것 없이 high의 값과 pivot의 값을 바꾸면 정확하게 맞아떨어진다. 

pivot 기준으로 왼쪽은 pivot보다 작은 값. 오른쪽은 pivot보다 큰 값.

개쩐다.. 5가 고정 되었다. 이걸 재귀로 왼쪽편, 오른쪽 편 쫘르륵 실행해주면 알아서 각각의 pivot들이 제 자리를 찾아 정렬된 결과를 딱 보일 수 있을 것이다. 

이런 방법을 어떻게 생각했단 말인가 진짜..

코드 및 실행 결과

----

----

QuickSort 함수에서 ' if (left <= right) ' 이 조건! 이 조건은 위 퀵 정렬 과정에서 row와 high 가 서로 넘어서는 경우와는 완전 다른 조건이다. 해당 조건은 쪼개짐의 범위에 대한 조건으로 left와 right가 서로를 넘어서는 것은 이미 요소 하나 단위까지 쪼개고 난 이후라는 의미이다.

잘 정렬되었다. 

병합 정렬에서 재귀에 대해 한 번 설명을 써본 탓에 이번엔 정신이 온전하다.

퀵 정렬의 성능

퀵 정렬의 빅오는 pivot을 어떤 것을 선택하느냐에 따라서 다르다. 잘 선택한 경우

최선의 경우 : O(n log 2 n) - 2는 아래 첨자 2이다.
최악의 경우 : O(n^2) 

최선의 경우를 잘 뽑도록 pivot을 데이터 세트의 특성 상 잘 뽑아야하고, 데이터의 이동이 적기 때문에 매우 효율적이고 빠른 알고리즘이라고 생각하면 되겠다.

오늘도 역시 공부해놨던 부분을 이제 포스팅하는 시간이다. 역시 미리미리 해야한다.

스택이란?

일단 그림이 먼저다.

A, B, C 순서로 사각형을 넣을 것이다.

이렇게 된다. 그렇다면 다시 뺀다면?

이 때, 담는 용기, 통! 이것이 스택 자료구조이다. 
먼저 들어간 사각형 A가 제일 늦게 나오는 구조인 것이다. 이러한 개념을 후입선출이라고 한다. 나중에 들어간 것이 먼저 나오는 구조!

이를 구현하면 아래와 같다.

코드 및 실행 결과

---

---

중간 중간에 보완해야할 부분이 있지만 개념 부분에서는 충분하기 때문에 보완하지는 않았다.

이번에는 병합 정렬이다. 이게 생각보다 간단하긴 한데 복잡하다(?) 일단 시작한다.

병합 정렬이란?

병합 정렬의 기본은 다음과 같다.

1. 배열을 원소 단위로 쭉~~ 나눴다가
2. 다시 단계적으로 정렬과 동시에 결합을 반복한다.

그림으로 나타내자면 다음과 같다.

그럼 문제는 무엇이냐? 어떻게 쪼갤 것인가? 이다. arr[0] , arr[1] 이게 쪼갠 것 아닌가? 아니다. 그냥 원소에 접근한거지 쪼갠게 아니다. 

그럼 쪼갠다 라는 의미를 아주 곰곰히 생각해봐야한다. 

쪼갠다는 것은 큰 덩어리부터 시작해서 작은 단위로 나눈다는 것이고, 내가 원소 레벨까지 쪼갰다 라는 의미는 내가 지금 쪼개고 있는 진행 흐름이 원소 단위까지 접근했다! 라는 것이다.

좀 어렵지만 잘 생각해라. arr[0] 에 접근하는 것은 우리 집 강아지와 할머니도 할 수 있는 행위이다.(집에 강아지와 할머니는 없다) 이것은 쪼갠 것이 아니고 접근한 거다. 

쪼갠다는 것은 그림의 설명과 같다.

제어할 수 있는 인덱스 범위를 한정지으면 되겠다 이것이다. 그런데 내가 가만히 보니 이 쪼개는 단계가 범위만 줄어드는 것 외에는 모두 같은 짓을 하고 있는 것이다. 그렇다면 원본 배열을 던지고, 그와 함께 범위 값만 다르게 던져주면 알아서 쪼개주는 함수가 없으려나?

있다. 바로 재귀 함수이다. 바로 코드를 본다

위 함수처럼 원본과 범위를 지정하여 함수에 던져주면 알아서 반으로 쪼갤 것이다. 

위 그림처럼 될 것이다.

그렇다면 쪼갰으니 정렬과 결합을 해야한다. 다시 MergeSort 코드를 보겠다.

MergeSort는 범위를 나누어 두 토막 내고(2개의 MergeSort) 그리고 정렬과 결합을(Merge) 수행한다 라는 사실을 기억해야하며, 신뢰해야한다. 그니까 밑에 잔뜩 실행된 MergeSort 함수는 신경쓰지말고, 현재 주어진 범위들에 대해서 정렬하고 결합한다는 것이다.

위 그림처럼 밑 바닥까지 MergeSort 하면서 내려가면 더 이상 쪼개지 못하므로 각 MergeSort에게 지정된 범위에 대해서 Merge 를 통해 정렬과 결합을 수행해주고 리턴한다 그러면 한 단계 위층에서의 MergeSort들은 내부적으로 정렬된 두 덩어리를 받을 것이고 또한 그들도 Merge 를 통해 정렬과 결합을 수행해주고 리턴해준다. 언제까지? 다 합쳐질 때까지!

물론!!!! 여기서 정렬은 조상님이 와서 대신 해주는게 아니다! Merge라는 함수 내에서 이를 구현해야한다. 이는 어렵지 않으므로 코드로 확인해보면 될 것이다.

이 코드가 핵심인데, 앞 범위 토막과 뒷 범위 토막의 요소들을 모두 둘둘씩 비교하여 작은 값을 새로운 공간에 차곡차곡 넣는 방식이다. 이게 가능한 이유는 각 토막들은 아래 계층에서 이미 정렬되어 올라왔기 때문이다! (쓰면서 명확히 깨달음 ㅋ)

내가 무슨 말을 하고 있는지 모르겠다면 직접해봐라 미래의 나야

코드 및 실행 결과

----

----

머리가 참 아득해진다..

머리가 아득해지는 김에 빅오를 보자

병합 정렬 성능

최악/ 평균 / 최선에 상관없이 비교와 데이터 이동 연산을 모두 세어보면 O(n log 2 n)이다. 2는 아래 첨자 2이다.

오늘은 힙 정렬이다.

힙 정렬이란?

말 그대로 Heap 자료구조를 이용한 정렬 방식이다. Min Heap에서 루트 노드부터 빼오면 오름차순 정렬이 가능한 점을 이용해한 것이다.

힙 정렬은 Heap 자료 구조 조금 개조하면 만들 수 있다.
아래 그림과 같은 Min-Heap을 이용하면 정렬 성능이 죽여준다 ㅋ 

우선 순위 큐에서도 우선 순위가 높은 것을 작은 값이라고 약속하고 작성한다면 같은 결과이다. 뭐 그 기반이 heap 자료구조이니 heap을 통해서 구현했고, 이미 구현해놓은 것에 우선 순위 부분만 조금 수정하였다. 나중에 기억 안날 때에는 아래 링크 먼저 보고, 다음 코드를 확인하면 될 듯 하다. 

수정한 부분을 보자면, 원래 기존 heap 코드는 우선 순위를 결정하는 부분을 삽입마다 지정하기로 했는데 그것을 함수 포인터를 이용하여 없애버리고 자동으로 우선 순위를 나뉘도록 했다.

https://typingdog.tistory.com/110?category=924874

다음은 코드이다.

코드 및 실행 결과

----

----

힙 정렬 성능

힙 데이터 저장 시간 복잡도 : O(log2 n) - 2는 아래 첨자의 2이다.
힙 데이터 삭제 시간 복잡도 : O(log2 n) - 2는 아래 첨자의 2이다.
힙 데이터 정렬의 경우, 저장과 삭제를 각각 n번씩 수행하므로 시간 복잡도 : O(n log 2 n) - 2는 아래 첨자의 2이다.

힙 구조에 데이터 삽입, 삭제 등이 이루어진다는 것을 고려한다고 하더라도, 앞서 봤던 O(n^2) 정렬들 보다도 성능이 좋은 것이다.

하 코딩해놓고 묵혀뒀다가 포스팅하느라 다시 보고 시간 버리는게 너무 아깝다 앞으로는 정말 열심히 바로바로 정리해서 올려야겠다.

그래도 다시 복습할 기회가 되었으니 의미있는 시간이라 생각하고 일반 연결 리스트에 대한 기록이다.

내가 (윤성우 교수님의 자료구조 책의 ADT를 보고) 코딩한 연결 리스트는 살짝 형태가 다르다. 그러므로 특징에 대해서 그림과 글의 적절한 특징 설명 이후 코드와 실행결과를 기록 하겠다.

일단,

단순 연결 리스트란?

구조체와 주소 값을 이용하여 현재 노드 내부에 다음 순서 노드의 주소 값이 저장되어 있는 형태로 이 이어진 연결을 통해 값을 순회할 수 있는 자료 구조이다.

노드 내부에 다음 순서 노드의 주소 값이 저장되어 있다는 것은 이러한 경우를 뜻한다.

구조

원래는 아래 그림과 같은 형식으로 리스트가 구성되어졌어야 했는데 

머리 회전이 덜 된 관계로 아래 처럼 다른 리스트를 만들어버렸다. 그건 뭐 그거대로 기록할 것임.

일단 위 구조로 생겨먹었고, 노드 구조체와 그 노드들을 담고 관리하는 자료구조 구조체가 있다

새 노드가 항상 헤드 다음 즉, 실질 데이터 노드 맨 앞에 항시 존재해야만 한다. 값을 추가할 때, 값과 링크 값만 변경하고 사용한다. 위와 같은 특성 때문에 리스트를 초기화할 때 다음 그림과 같이 꼭 -1 값으로 초기화 한다.

초기화 및 추가

값을 추가할 때에는 빈 노드의 값을 변경하여 사용하지만, 그래도 어찌됐던 빈 노드를 헤드 다음, 데이터 노드들 맨 앞에 두는 것이 원칙이기 때문에 데이터를 추가할 때 빈 노드 또한 추가해 놓아야 한다.

순회
다음은 순회이다.

삭제 
다음은 삭제이다. 내가 따로 만든 함수들이 있기 때문에 간단하게 설명한다.

코드 및 실행 결과

----

----

메모리 관리가 중요한 것 같다.ㅋ

삽입 정렬 어렵진 않은데 뭔가 설명을 적기에는 복잡하다 휴 영상이면 좋을텐데 말이지

일단 기록해둔다.

삽입 정렬이란?

삽입해서 정렬하는 것이다. 예를 들어서 

이와 같은 배열이 있을 때, 아래의 그림 순으로 설명하겠다.

그림으로 설명을 좀 대체했다. 나중에 알아먹을 수 있을란가 모르겠군.

그리고 각 그림 속 번호는 그림을 처음 봤을 때 읽어야 할 순서의 동글뱅이 번호를 뜻한다.

코드 및 결과

----

----

삽입 정렬 성능

이미 정렬되어있는 부분들이 많을수록 성능은 좋다.

최악의 경우 비교, 대입 횟수는 버블 정렬과 마찬가지로 O(n^2) 이다
왜냐하면 안쪽, 바깥쪽 반복의 횟수가 일치하기 때문이다.

최악의 경우 비교 횟수 : (n-1) + (n-2) + ... + 2 + 1 -> O(n^2)
최악의 경우 대입 횟수 : (n-1) + (n-2) + ... + 2 + 1 -> O(n^2)

오늘도 짤막하게 코딩해보고 바로 포스팅한다. 이렇게 하니 매우 여유있게 보고 정리할 수 있는 것 같아서 좋다.
선택 정렬 또한 간단하다 ㅋ

선택 정렬이란?

위와 같은 배열이 있다. 이를 오름차순으로 정렬할 예정이다.

버블 정렬이 이전 요소들 앞뒤를 비교해가면서 결국, 맨 마지막 대상을 확정 짓는 것이라면 선택 정렬은 반대이다.

맨 왼쪽 요소를 확정 지어가면서 범위를 좁혀나가는 것인데, 버블 정렬처럼 비교한 후 더 변경할 조건이 맞는 경우 값을 교환하는 것이 아니라 변경할 '인덱스'를 저장해 둔 후, 자리를 확정 지을 때 이 인덱스를 활용하여 교환을 한다.

!! 수정 !! :: 3번 동그라미에서 1(인덱스 2)는 1(인덱스 3)로 변경되어야 합니다!!!!!!!!!!!!!!!!!!!!!

코드 및 실행 결과

----

9번 라인에서 i의 조건을 n-1 미만으로 두는 이유를 다음 그림을 통해서 설명하겠다.

----

선택 정렬 성능

최악의 경우 비교 횟수 : (n-1) + (n-2) + ... + 2 + 1 -> O(n^2)
최악의 경우 대입 횟수 : n-1 회 무조건 대입이 일어난다. -> O(n)

버블 정렬에 비하면 양호하지만 버블 정렬에서는 최선의 경우에는 한 번도 대입 연산이 없을 수 있으므로, 비교하기 난감할 뿐이다.

버블 정렬을 학습 후에 바로 정리한다.

버블 정렬이란?

위와 같은 4칸 크기의 배열 구조가 존재하고 그 안에 값이 정렬되지 않은 채로 존재한다. 여기서 우리는 오름차순으로 값을 정렬하고자 한다.

각 화살표 시작에 적힌 원 숫자 순서대로 값을 결정하는 방법이다. 어떻게? 인덱스를 하나씩 증가시켜가면서 인덱스와 뒤 인덱스를 비교하여 값의 위치를 조정하는 것. 그것이 버블 정렬이다.

총 4개의 값이 들어왔다고 가정.

3번째 자리, 2번째 자리, 1번째 자리, 0번째 자리 순으로 값이 정해져야 한다.

(1) 3번째 자리에 들어올 값을 정하기 위해서는 [0]과 [1](0+1)을 비교, [1]과 [2](1+1)를 비교, [2]와 [3](2+1)을 비교 ( 3번 반복 ) -> 3번째 자리에 들어올 값 결정

(2) 2번째 자리에 들어올 값을 정하기 위해서는 [0]과 [1](0+1)을 비교, [1]과 [2](1+1)를 비교 ( 2번 반복 ) -> 2번째 자리에 들어올 값 결정
(3) 1번째 자리에 들어올 값을 정하기 위해서는 [0]과 [1](0+1)을 비교 ( 1번 반복 ) -> 1번째 자리에 들어올 값 결정
(4) 0번째 자리에 들어올 값은 자연스럽게 결정

결국 총 3번 반복하는데 그 반복 하나하나마다 3번, 2번, 1번 반복을 해야한다.
이를 코드로 나타낸다면

for ( ... )
{
    for( ... )
    {
        ...
    }
}

이러한 형태가 되는 것이다.

코드 구현 및 실행 결과

----

----

버블 정렬 성능

최악의 경우 비교 횟수 : (n-1) + (n-2) + ... + 2 + 1 -> O(n^2)
최악의 경우 대입 횟수 : 비교 후 바로 대입이 진행되므로 O(n^2), temp 연산으로 인한 *3 -> 3 * O(n^2) -> O(n^2)

공부하고 나면 그 때 그 때 정리해야한다는 것을 뼈저리게 느끼는 시작이다..

이번에 정리할 내용은 단순 배열 리스트이다. 다만, 그냥 배열을 쫘르륵 순회하고, 삭제 띡 하고, 추가하고 그러면 일반 배열 사용법을 정리하는 것과 다를 바가 없으므로, 약간 형식이 있는 리스트 틱한 배열로 만들어 정리한다ㅋㅋ

일단은 정의와 특징, 장 단점을 간단하게 상기시키며 넘어가도록 하겠다.

단순 배열 리스트란?

말 그대로 단순한 배열이다. 그런데 리스트라는 자료구조 형태이므로 메모리 공간 뿐만 아니라 삽입, 삭제, 탐색에 대한 함수를 추가 보완함으로써 하나의 자료 구조로 완성을 시킬 셈이다.

배열 리스트의 장점

Random Access, 임의 접근이 인덱스를 기반으로 가능하기 때문에 데이터의 참조가 쉽다.  O(1) <- 개쩐다ㄷㄷ

배열 리스트의 단점

배열의 길이가 초기에 결정되며, 이 길이는 변경이 불가능하다.
삭제 과정에서 데이터의 이동이 매우 많이 일어난다.
탐색할 경우 최악의 경우에는 O(n)이다. <- 매우 성능이 나오지 않는 것이다. 데이터의 수에 매우 정비례하여 시간이 늘어나기 때문이다.

코드 구현 및 실행

---

---

공부를 하고 정리하는 것이 매우 중요하다. 근데 그 정리를 하기가 조금 귀찮은 것이 아니다. 앞으로는 그 때 그 때 정리하도록 하고, 모아두지 말아야겠다.. 업로드 할 것이 한 두 가지가 아니다ㅜㅜ

자료구조 공부의 순서에 상관없이 그냥 올리려고 한다.

오늘은 우선 순위 큐를 위한 Heap 자료 구조에 대해서 정리한다. 큐 형태로 포장하지 않았을 뿐이지, 큐를 염두하여 만들었기 때문에 큐라고 이름만 바꾸면 우선 순위 큐가 될 수 있다.

Heap 이란 무엇인가?

힙이란 다음 그림과 같은 형태이다.

Q : 엥? 이건 (완전) 이진 트리가 아닌가? 
A : 그렇다. 맞다
- 빼박 이진 트리 아닌가? 의미의 '완전'이 아니다, 리프 노드를 제외한 모든 노드들은 두 자식 노드를 꼭 채워진 형태의 트리, 리프 노드는 꼭 왼쪽부터 채워지는 트리를 의미하는 '완전 이진 트리'

이 친구들은 이진 트리의 형태를 하고 있으나, 일반 이진 트리와는 달리 좀 많은 규칙들로 탄탄히 채워진 트리이다. 이 규칙들을 통해 힙의 특징을 설명할 것이다.

Heap 의 특징

1. 완전 이진 트리의 특성을 갖는다.
리프 노드를 제외한 모든 노드들은 두 자식 노드를 모두 채운 상태여야하며, 리프 노드는 채울 때, 왼쪽부터 채워져야 한다.

2. 자식 노드와 부모 노드 간의 규칙이 존재한다.
힙은 밑에서 부터 쌓아 올리는 자료 구조이기 때문에 부모 노드와 자식 노드 간 특정한 규칙이 존재한다. 예를 들어, 자식 노드는 부모보다 커야만 한다, 자식 노드는 부모보다 작아야만 한다 등의 규칙이다. 

3. 일반적인 트리와 달리, 왼쪽 자식과 오른쪽 자식은 부모 노드 기준으로 값이 작은 노드와 큰 노드로 취급하지 않는다. 
그저 리프 노드의 자식을 채울 때, 왼쪽에서 오른쪽 순으로 먼저 채우는 것 뿐이다.

힙 구조에 값을 삽입

트리의 가장 끝에 삽입 후 부모와 비교하여 위치를 조정한다.

힙 구조에서 값을 삭제

삭제할 때에는 탐색 후 삭제가 아니라, Pop의 개념이다. 루트 노드의 값을 빼준다. 그리고 나서 꼭 트리를 재구성 해줘야하는데 이 때, 루트를 어떤 값으로 채울 것인가에 대한 고민을 해야한다. 그러기 위해서는 가장 마지막 노드를 루트에 넣고 트리를 재구성하여 내려간다.

이와 같은 구조에서 3을 제거하고, 10을 루트에 넣어본다.

10을 루트에 넣고 보니 위배되는 부분들이 존재한다. 이를 풀기 위해 계속 구조를 재조정한다.

이 값을 삭제하는 부분으로 인해 우선 순위 큐의 구현이 가능하다!!!

우선 순위 큐란 무엇인가? 우선 순위가 높은 것을 먼저 빼는 것이다. 큐의 선입선출 이딴 거 다 필요없고, 언제 들어가든 간에 우선 순위가 높은 것이 먼저 나오는 것이다.
단, 우선 순위가 같은 경우에는 선입선출이 보장되어야 한다. 이는 리프노드의 왼쪽 삽입 우선 특징(1번 특징)으로 인해서 같은 우선 순위의 경우 선입 선출을 보장하도록 프로그램을 작성할 수 있다. 

즉, 힙의 루트 노드는 삽입, 삭제 과정에서의 힙 자료구조의 재조정을 통해 각 힙에서 지정한 규칙에 의거하여 우선 순위가 높은 값으로 채워넣어진다.
예를 들어

Max Heap의 경우에는 루트 노드로 올라갈수록 값이 커짐 -> 큰 값일 수록 우선 순위가 높다.
Min Heap의 경우에는 루트 노드로 올라갈수록 값이 작아짐 -> 작은 값일 수록 우선 순위가 높다.

사용자 정의 Heap의 경우에는 구조체 등을 이용하여 우선 순위 변수를 따로 두고 진행한다면 이 또한 우선 순위를 매길 수 있다.

이렇게 힙 구조에서 루트 노드에서 값을 빼냄으로써 우선 순위대로 값을 취할 수 있기 때문에 heap을 통한 우선 순위 큐를 구현할 수 있는 것이다.

힙의 구현

힙을 구현할 때에는 배열로 구현할 것이다. 왜냐?

그 이유를 알기 이전에 있어서 힙을 어떤 자료 구조로 구현할 수 있는지부터 확인해보자.

1. 완전 이진 트리이므로, 연결 리스트의 구조로 당연히 구현이 가능하다.
2. 그리고 인덱스 조절을 통한 배열로도 가능하다.

그렇다면 왜 배열로 구현할 것인가?
우리는 삽입 연산을 진행할 때, 트리의 가장 마지막 노드 자리에 값을 삽입한다. 만약 단순 연결 리스트로 구현했다면 이 마지막까지 순회하기에 비용이 많이 든다. 그리고 부모, 자식 간의 노드 비교가 많기 때문에 비교적 비용이 적게 드는 랜덤 엑세스가 가능한 배열로 구현하기로 했다. (라고 윤성우 교수님의 자료구조 서적에 나와있다 ㅋ)

그래서 인덱스 제어 방법이 필요하다.

1. 배열의 인덱스는 1부터 시작한다. ( 인덱싱을 용이하게 하기 위함이다. 구현하다보면 안다. 왜 인덱싱을 1부터 하는지 ㅋㅋㅋ)

2. 현재의 인덱스를 넣었을 때, 부모 혹은 자식의 노드를 구하는 방법을 알아야 한다.

위 그림과 같이 계산하면 임의의 인덱스를 기준으로 부모 노드의 인덱스를 구할 수도, 자식 노드를 구할 수 도 있다. 즉, 완전 이진 트리 구조라고 할지라도 인덱스를 통한 랜덤 엑세스가 가능한 것이다.

아래는 그 코드와 주석이다.

---

---