☑️ 힙 정렬

내가 아는 힙은 메모리밖에 없는디

개요

• 힙이란 무엇일까? 힙은 최솟값이나 최댓값을 빠르게 찾아내기 위한 완전 이진 트리 기반의 이진 트리이다
  • 완전 이진 트리 : 데이터가 루트 노트부터 시작해 자식노드가 왼쪽부터 들어가는 이진 트리
• 따라서 최대힙과 최소힙이 존재한다
  • 최대 힙: 부모 노드가 자식 노드보다 큰 힙 ➡️ 맨 위의 원소가 가장 크다
  • 최소 힙: 자식 노드가 부모 노드보다 큰 힙 ➡️ 맨 아래의 원소가 가장 크다
• 힙 정렬은 힙 구조를 "이용"한다. 즉 힙 생성 알고리즘을 사용한다
• 하나의 원소에 대해 힙 생성 알고리즘의 시간 복잡도는 O(log n) 이다
  • 트리의 높이만큼만 계산을 해주면 되기 때문이다
• 따라서 n개의 원소를 가진 트리 전체를 힙 구조로 만들기 위해선 n * log n 의 시간이 소요된다
• 힙 정렬의 전체 시간 복잡도 또한 O(n * log n) 이다
• 추가적인 배열이 필요하지 않은 점에서 메모리 측면에서 굉장히 효율적
• 힙 생성 알고리즘은 상향식 구현 방식과 하향식 구현 방식이 있다
  • 헷갈리지 않아야 할 점은 하나의 원소에 대한 상향식, 하향식 이라는 것이다. 최대(또는 최소)힙을 구현하기 위해선 모든 원소에 대해 적용해야 한다. 즉 2중 반복문을 사용해야 할 것이다

알고리즘

• 정렬할 데이터들을 최대힙으로 만든다
• 루트의 값을 가장 뒤의 값과 바꾸고 힙 트리의 크기를 하나 줄인다 크기를 줄인 트리에 대해 힙 정렬을 수행한다 ➡️ n번 반복 (따라서 시간복잡도가 O(n * log n) 인 것이다)

구현

		for (int i=number-1;i>=0;i--){ //모든 원소에 대해
         int c=i; //특정 원소에 대해
         do { //힙 생성 시작 (하향식으로)
             int child=c*2+1;
             if (child<number-1&&heap[child]<heap[child+1])
                 child++;
             if(child<number&&heap[child]>heap[c]){
                 int temp=heap[c];
                 heap[c]=heap[child];
                 heap[child]=temp;
             }
             c=child; //계속 아래로 내려갈 거니까
         }while(c<number);
     }

• ⭐하향식으로 할 경우 아래에서 위로 순회하도록 반복문을 설정해야한다. 그 원소부터 아래의 원소들은 모두 정렬이 완료된 상태를 가정하기 때문이다.
  따라서 상향식으로 할 경우 특정 원소가 위에서 아래로 이동하도록 반복문을 설정해야 한다 for(int i=0;i<number;i++)
• 트리의 성질을 이용하여 자식 노드를 구하고 2개의 자식 노드 중 더 큰 것을 찾는다
  • 왼쪽 자식 노드스 = 부모 노드 인덱스 * 2+1
  • 오른쪽 자식 노드 인덱스= 부모 노드 인덱스 * 2+1
  • 부모 노드 인덱스 = (자식 노드 인덱스 -1)/2
• 부모 노드가 자식 노드보다 작을 경우 swap
• 하향식이므로 현재 원소가 자식 노드로 이동하여 정렬을 반복 진행한다

		for (int i=number-1;i>=0;i--){//모든 원소에 대해
            int temp=heap[i];
            heap[i]=heap[0];
            heap[0]=temp;// 최대값이랑 맨 뒤 값이랑 swap
            int root=0;
            int child=1; //while에 조건 걸어야 돼서 여따가 선언
            do {
                child=root*2+1;
                if (child<i-1&&heap[child]<heap[child+1])
                    child++;
                if(child<i&&heap[child]>heap[root]){
                    temp=heap[root];
                    heap[root]=heap[child];
                    heap[child]=temp;
                }
                root=child;
            }while(child<i);
        }

• 정렬을 시작
• root 원소와 맨 뒤 원소를 swap (이 때 맨 뒤로 간 root 원소는 정렬이 끝난 것이다)
• 새로 만들어진 힙 트리를 다시 최대힙으로 만든다
• 이 때 힙의 크기를 하나씩 줄이기 위해 child가 number가 아닌 i보다 작을 때로 조건을 설정한다 (i는 반복문이 진행될수록 작아지기 때문)

하 ... 멍청이