힙 정렬


난이도 중급
자주 묻는 질문 24 * 7 Innovation Labs 아마존 Apple 벨자바르 인튜이트 신탁 삼성 SAP SAP 연구소 비자,
배열 정렬

힙 정렬은 이진 힙 데이터 구조를 기반으로하는 비교 기반 정렬 기술입니다. HeapSort는 최대 요소를 찾은 다음 해당 요소를 끝에 배치하는 선택 정렬과 유사합니다. 나머지 요소에 대해서도 동일한 프로세스를 반복합니다.

정렬되지 않은 배열이 주어지면 힙 정렬을 사용하여 정렬합니다.

여기에서 주어진 입력은 정렬되지 않은 배열이며 힙 정렬을 사용하여 배열을 정렬해야합니다.

입력: 9,5,1,6,11,8,4

산출: 1,4,5,6,8,9,11

힙 정렬 알고리즘

  • HeapSort는 비교 기반 알고리즘으로 배열의 끝에 최대 요소를 배치하고 배열 전체가 정렬 될 때까지 나머지 배열 요소에 대한 프로세스를 반복합니다.
  • 힙 정렬은 배열에서 이진 최대 힙을 빌드합니다. 최대 힙은 트리 데이터 구조입니다. 여기서 모든 부모 노드는 자식 노드보다 큽니다.
  • 배열 arr []는 이진 트리로 나타낼 수 있습니다.
    1. arr [0] 루트 노드입니다.
    2. 왼쪽 아이들의 색인 = 2 * i + 1
    3. 오른쪽 자녀 색인 = 2 * i + 2

어디에 i 부모 노드의 인덱스입니다.

  • 이진 트리는 다음을 사용하여 이진 힙으로 변환됩니다. 힙화 이 작업은 자식 노드보다 큰 부모 노드의 값을 유지합니다 (최대 힙). 상위 노드가 하위 노드보다 작 으면 상위 노드를 값이 가장 큰 하위 노드로 바꿉니다.

최대 힙 작업의 예

아래는 루트 값이 0, 왼쪽 자식이 5, 오른쪽 자식이 4 인 트리의 최대 힙 연산입니다.

힙 정렬

암호알고리즘

힙 정렬 알고리즘에서는 주로 두 가지 기능을 사용합니다.

  1. heapServe (arr, i, n) – 힙화 ith 노드 arr []
  2. heapsort (arr, n) –
    1. 먼저 전체 배열을 힙화합니다 (리프가 아닌 노드를 힙화하여).
    2. 루트에서 가장 큰 요소를 추출합니다.
    3. 배열의 마지막 요소로 바꿉니다.
    4. 완전히 정렬 된 배열을 얻을 때까지 프로세스 a, b, c (순서대로)를 반복합니다. 어디 a heapServe (힙 정렬을위한 서비스 함수), b heapSort이고 c 추출물 뿌리입니다.

힙 정렬

힙 정렬

힙 정렬

힙 정렬을위한 C ++ 프로그램

#include <iostream>
using namespace std;

// service function to heapify array
void heapServe(int arr[],int i,int n)
{
    int large = i;
    // index of left and right child
    int left = 2*i+1;
    int right = 2*i+2;

    // find largest amongst parent ,left and right children
    if(left < n && arr[left] > arr[large])
    large = left;
    if(right < n && arr[right] > arr[large])
    large = right;

    // swap if parent node is not largest
    // recursiveley heapify swapped nodes
    if(large != i)
    {
        swap(arr[i],arr[large]);
        heapServe(arr,large,n);
    }
}

// function to sort the array
// Parent node is node that has atleast one children
void heapSort(int arr[],int n)
{
    // Index of last/right most parent node
    int last_non_leaf = n/2 - 1;

    // heapify the array beginning from right most parent node
    for(;last_non_leaf >= 0;last_non_leaf--)
    heapServe(arr,last_non_leaf,n);
    
    // start sorting from rightmost of the array
    for(int i=n-1;i >= 0;i--)
    {
        // Extract root (largest) element,swap with last array element
        swap(arr[0],arr[i]);
        // heapify the leftover array (obtained after extracting largest element)
        heapServe(arr,0,i);
    }
}

int main()
{
    int arr[] = {9,5,1,6,11,8,4};
    int n = sizeof(arr)/sizeof(arr[0]);

    heapSort(arr,n);

    for(int i=0;i<n;i++)
    cout<<arr[i]<<" ";
    
    return 0;
}

산출

1 4 5 6 7 8 9

힙 정렬을위한 Java 프로그램

class heap
{
    // service function to heapify array
    public static void heapServe(int arr[],int i,int n)
    {
        int large = i;
        // index of left and right child
        int left = 2*i+1;
        int right = 2*i+2;

        // find largest amongst parent ,left and right children
        if(left < n && arr[left] > arr[large])
        large = left;
        if(right < n && arr[right] > arr[large])
        large = right;

        // swap if parent node is not largest
        // recursiveley heapify swapped nodes
        if(large != i)
        {
            int temp = arr[large];
            arr[large] = arr[i];
            arr[i] = temp;
            heapServe(arr,large,n);
        }
    }
    // function to sort the array
    // Parent node is node that has atleast one children
    public static void heapSort(int arr[],int n) 
    {
        // Index of last/right most parent node
        int last_non_leaf = n/2 - 1;
        
        // heapify the array beginning from right most parent node
        for(;last_non_leaf >= 0;last_non_leaf--)
        heapServe(arr,last_non_leaf,n);

        // start sorting from rightmost of the array
        for(int i=n-1;i >= 0;i--)
        {
            // Extract root (largest) element,swap with last array element
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            
            // heapify the leftover array (obtained after extracting largest element)
            heapServe(arr,0,i);
        }
    }

    public static void main(String args[]) 
    {
        int arr[] = {9,5,1,6,11,8,4};
        int n = arr.length;

        heapSort(arr,n);

        for(int i=0;i<n;i++)
        System.out.print(arr[i]+" ");
    }
}

산출

1 4 5 6 7 8 9

HeapSort의 복잡성 분석

  • 힙화의 복잡성은 O (logn)이며, 각 요소를 추출하는 데는 O (n) 시간이 걸리고 전체 복잡성 T (n) = O (nlogn)이 걸립니다.
  • 최상의 경우 : T (n) = O (nlogn)
  • 최악의 경우 : T (n) = O (nlogn)
  • 평균 사례 : T (n) = O (nlogn)
  • 보조 공간, A (n) = O (1)

HeapSort에 대한 추가 정보

  • HeapSort는 Inplace 정렬 알고리즘입니다.
  • 힙 정렬은 안정적인 알고리즘이 아닙니다.
  • Quicksort 및 Merge Sort는 재귀 호출로 인해 일정한 시간 오버 헤드가 있으므로 HeapSort보다 성능이 더 좋습니다.

참고

https://en.wikipedia.org/wiki/Heapsort

관련 기사

연결 목록의 빠른 정렬보다 병합 정렬이 더 좋습니다.