힙 정렬 예제

우리는 최근에 엄격한 규칙 집합을 따르고 우선 순위 큐 및 백그라운드 작업과 같은 것을 구현하는 데 사용되는 특수 한 종류의 이진 트리인 힙을 좋아한다는 것을 배웠습니다. 그러나 이것만이 힙이 좋은 것은 아닙니다. 이진 힙은 효율적인 정렬 이외의 다른 용도로 사용되는 경우가 많습니다. 배열을 정렬하는 가장 효율적인 방법 중 하나가 되기 때문에 많은 프로그램이 힙 정렬에 의존합니다. 그리고 이제 힙이 무엇인지 알게되었으므로 정렬 문제에 관해서 왜 그렇게 잘 작동하는지 이해하려고 노력할 수 있습니다! Introsort는 빠른 정렬과 힙정렬을 결합하여 최악의 경우 힙정렬 속도와 빠른 정렬의 평균 속도 라는 장점을 모두 유지하는 힙정렬의 대안입니다. 힙정렬은 1964년 J. W. J. 윌리엄스에 의해 발명되었습니다. [2] 이것은 또한 그 자체로 유용한 데이터 구조로 윌리엄스에 의해 이미 제시 된 힙의 탄생이었다. [3] 같은 해에 R.

W. Floyd는 배열을 제자리에 정렬할 수 있는 개선된 버전을 발표하여 트리정렬 알고리즘에 대한 이전 연구를 계속했습니다. [3] 힙 정렬은 정렬될 때 전달되는 배열을 변환합니다. 일부 정렬 알고리즘과 달리 입력 데이터의 완전히 별도의 복사본을 만들지는 않습니다. 이렇게 하면 내부 정렬 알고리즘이 됩니다. 힙 정렬은 외부 메모리가 필요하지 않으며 내부 정렬 알고리즘입니다. 반복적으로 실행되고 재귀적이지 않으므로 heapify 함수를 교환하고 호출할 때 한 번에 두 요소를 비교하여 비교 정렬 알고리즘으로 만듭니다. 멋진! 이제 루트 노드였던 가장 큰 요소인 19가 이제 배열의 마지막 위치에 있음을 알 수 있습니다. 그리고 나머지 요소에 대해 효과적으로 “정렬”되므로 힙에서 완전히 제거 할 수 있습니다.

상향식 힙정렬은 중요한 요인에 의해 요구되는 비교 수를 줄이는 변형입니다. 일반 힙정렬은 2n log2n + O(n) 비교가 최악의 경우와 평균적으로 필요하지만[8] 상향식 변형은 n log2n + O(1) 평균 비교,[8] 및 최악의 경우 1.5n log2n + O(n)를 비교해야 합니다. [9] 힙 종류는 존 윌리엄스에 의해 발명되었다. 힙 정렬은 선택 정렬과 반대되는 접근 방식을 사용하는 데이터 구조의 정렬 기법입니다. 선택 정렬은 n 요소 중 가장 작은 요소를 찾은 다음 n-1 요소 중 가장 작은 요소를 찾습니다. 배열 힙 정렬의 끝이 가장 큰 요소를 찾아 배열의 끝에 배치 할 때까지 두 번째로 큰 요소가 발견되고 이 프로세스가 다른 모든 요소에 대해 반복됩니다 두 번째 단계에서는 정렬 된 배열이 반복적으로 가장 큰 요소를 이리저리 제거하여 만들어집니다. m 힙(힙의 루트)을 입력하고 배열에 삽입합니다. 힙 속성을 유지 하려면 각 제거 후 힙 업데이트 됩니다.

힙에서 모든 개체가 제거되면 정렬된 배열이 생성됩니다. 힙 정렬은 힙 데이터 구조에서 수행됩니다. 힙이 완전한 이진 트리라는 것을 알고 있습니다. 힙 트리는 두 가지 유형이 될 수 있습니다. 최소 힙 또는 최대 힙. 최소 힙의 경우 루트 요소는 최소이고 최대 힙의 경우 루트는 최대입니다. 힙을 형성 한 후 루트에서 요소를 삭제하고 루트로 마지막 요소를 보낼 수 있습니다. 이러한 교환 절차 후 전체 배열을 다시 힙해야 합니다. 루트에서 요소를 삭제하면 전체 배열을 정렬 할 수 있습니다. 아래 알고리즘에서는 힙을 빌드하기 위해 heapify()를 호출하는 처음에 힙정렬() 함수가 호출됩니다. 힙은 배열정렬에 사용할 수 있습니다.

최대 힙에서 최대 요소는 항상 루트에 있습니다. 힙 정렬은 힙의 이 속성을 사용하여 배열을 정렬합니다. 힙은 다음과 같은 특수 힙 속성을 조정하는 특수 트리 기반 데이터 구조입니다.

Uncategorized