메모리 관리의 힙은 풀과 비슷합니다. 있다StackOverflow에서의 토론, 우리는 이 다른 것에 대한 세부 사항에 대해 이야기하지 않습니다.우리는 알고리즘과 데이터 구조의 힙 개념에 대해 이야기하고 있다는 것을 알고 있습니다.우리는 여전히 다음의 스타일을 따릅니다.알고리즘 소개.힙은 배열로 표현되는 완전한 이진 트리입니다.이진 트리는 한 종류의 트리이며, 모든 부모 노드에는 최대 2개의 자식이 있으며, 이를 왼쪽 하위 트리와 오른쪽 하위 트리라고 부릅니다.
완전 이진 트리는 레이어 개수가 k일 때 이진 트리입니다.케이
-1 노드.이와 같이:그리고 완전한 이진 트리는 완벽한 이진 트리 누출이거나 일부 노드가 부족하지 않지만 노드를 위에서 아래로, 왼쪽에서 오른쪽으로 채워야 한다고 생각할 수 있습니다.
이는 오른쪽의 일부 노드만 부족할 수 있음을 의미합니다.이와 같이:
이 완전한 이진 트리를 저장하기 위해 힙을 사용할 때 [A, B, C, D, E, F, G, H, I, J, K, L]과 같은 배열로 저장할 수 있습니다.이 저장 방법을 사용하면 이 트리의 루트 인덱스가 1이라는 것을 알 수 있습니다.
그리고 모든 상위 노드의 인덱스는 하위 노드의 인덱스를 2로 나눈 것입니다. 그리고 왼쪽 하위 노드의 인덱스는 상위 노드의 인덱스 곱셈 2이고 오른쪽 하위 노드의 인덱스는 상위입니다.노드의 인덱스에 2를 곱한 다음 1을 더합니다.
따라서 우리는 하위 노드와 상위 노드에 액세스하는 기능을 얻습니다.
그런 다음 Max-Heap이라는 데이터 구조에 대해 논의합니다.그것은 모든 부모가 자식보다 더 큰 더미입니다.따라서 우리는 Max-Heap 루트에서 가장 큰 숫자라는 것을 알고 있습니다.그림은 Max-Heap과 해당 배열입니다.
최소 힙을 쉽게 정의할 수 있지만 지금은 이에 대해 논의하지 않습니다.
a의 노드인 경우최대 힙하위 노드보다 작으므로 최대 힙 규칙을 위반합니다.해당 하위 노드가 유효한 최대 힙이라는 것을 알고 있는 경우 다음을 통해 이를 수정할 수 있습니다.최대 힙화작업.단계는 이 노드와 가장 큰 하위 노드의 값을 비교하는 것입니다. 상위 노드가 아닐 경우 가장 큰 하위 노드를 상위 노드와 교환합니다.그런 다음 하위 노드와 그 하위 노드를 검사합니다.단계별로 작업 후 최대 힙이 유효한지 확인할 수 있습니다.
비디오 데모를 만들고 있는데, 4는 오류 노드입니다.
이것이 코드입니다._A는 힙을 저장하는 배열이고, Java 배열의 인덱스는 0부터 시작하므로 인덱스는 -1입니다.
Max-Heapify를 실행하려면 도우미 함수 교환을 작성합니다.
그렇다면 임의의 완전 이진 트리에서 어떻게 Max-heap을 구축할 수 있습니까?다음과 같은 힙이 있다고 가정해 보겠습니다.
힙의 중간(5번째 노드)부터 시작하여 하나씩 루트로 돌아가 max-heapify 작업을 수행할 수 있습니다.완료되면 최대 힙이 생성됩니다.이에 대한 데모 비디오는 다음과 같습니다.
다음과 같이 코드하세요:
주의 깊게 살펴보면 max-heap이 정렬된 데이터 구조가 아니라는 것을 알 수 있습니다.모든 상위 노드는 하위 노드보다 크지만 왼쪽 하위 노드는 오른쪽 하위 노드보다 클 수도 있고 작을 수도 있습니다.어떤 방식으로든 이진 트리를 순회하는 것만으로는 순서가 지정된 배열을 쉽게 얻을 수 없습니다.그렇다면 힙을 사용하여 숫자를 정렬하려면 어떻게 해야 할까요?
우리는 뿌리가 항상 가장 큰 뿌리라는 것을 알고 있습니다.따라서 루트를 마지막 노드와 교환한 다음 힙에서 마지막 노드를 제거하고 루트를 최대 힙화할 수 있습니다.그런 다음 나머지 힙은 유효한 최대 힙이 되며 이 작업을 반복해서 수행할 수 있습니다.우리는 항상 가장 큰 숫자를 뒤에 두므로 순서가 지정된 배열을 얻습니다.
이 최대 힙에서 정렬을 시작할 수 있습니다.
이것은 우리의 데모 비디오입니다:
다음과 같이 코드하세요:
그리고 max-heap은 작업을 지원할 수 있습니다.ExtractMax, 루트를 반환하고 제거한 후 힙을 축소합니다.먼저 정렬하지 않고 이를 사용하여 최대 수 또는 k 가장 큰 수를 얻을 수 있습니다.다음과 같이 코드하세요:
따라서 max-heap을 사용하여 숫자를 정렬할 수 있습니다.또는 이를 사용하여 최대 수를 얻거나 정렬하는 것보다 더 적은 비용을 지불하기 위해 가장 큰 k 수를 얻을 수 있습니다.
GitHub 주소ï¼https://github.com/tinyfool/leetcode/blob/master/src/CLRS/HeapSort.java
힙 및 힙 정렬과 관련된 LeetCode 문제:
