힙소트란?

힙소트란?

• 힙트리의 성질을 이용해서 정렬

• 시간복잡도는 O(NlogN)이며, 공간복잡도는 O(1)이다.

• 시간복잡도가 O(NlogN)이지만, 참조 지역성의 원리로 보면 좋다고 할 수 없다.

• 부모 노드 1개와 자식 노드 2개의 구조를 이룬다.

• 비안정 정렬

구현 방법?

• 루트 노드가 왼쪽 서브 트리의 노드들보다 크고 오른쪽 서브 트리의 노드들보다도 큰 맥스힙트리를 만들어줘야 한다.

• 리프 노드에 가까운 노드들부터 힙트리의 성질을 만족하도록 구현한다.

• 힙트리의 성질을 만족시키고 난 후, 정렬이 필요하다.

• 맥스힙트리는 루트 노드가 가장 크므로, 루트 노드를 마지막 노드와 교환한다.

• 교환된 노드를 제외하고 나머지 노드들로 다시 루트 노드와 교환을 반복적으로 수행하면 된다.

자바 코드?

class Solution {
    void heapify(int[] nums, int idx, int range){
        int left = -1;
        int right = -1;
        int val = idx;
        
        while(true){
            left = 2 * idx + 1;
            right = 2 * idx + 2;
            
            if(left < range && nums[val] < nums[left])
                val = left;
            
            if(right < range && nums[val] < nums[right])
                val = right;
            
            if(val == idx)
                return;
            
            swap(nums, idx, val);
            idx = val;
        }
    }
    
    void swap(int[] nums, int idx1, int idx2){
        int tmp = nums[idx1];
        nums[idx1] = nums[idx2];
        nums[idx2] = tmp;
    }
    
    public int[] sortArray(int[] nums) {
        for(int i = nums.length / 2; i >= 0; i--){
            heapify(nums, i, nums.length);
        }

        for(int i = nums.length - 1; i >= 0; i--){
            swap(nums, 0, i);
            heapify(nums, 0, i);
        }
        
        return nums;
    }
}

시간복잡도 계산법?

• heapify 함수는 트리의 높이인 O(logN)의 시간복잡도가 발생한다.

• heapify 함수를 통해서 최대 N개의 데이터들을 다루고 있으므로 O(NlogN)이다.

• 항상 O(NlogN)의 시간복잡도를 가진다.