언제 힙을 사용하고 싶습니까?
Priority Queue의 분명한 대답 외에도 힙은 언제 프로그래밍 모험에 유용할까요?
가장 큰 (또는 가장 작은) 항목에 대한 빠른 액세스가 필요할 때마다 사용하십시오. 해당 항목은 항상 배열의 첫 번째 요소이거나 트리의 루트에 있기 때문입니다.
그러나 나머지 배열은 부분적으로 정렬되지 않은 상태로 유지됩니다. 따라서 즉시 액세스는 가장 큰 (가장 작은) 항목에만 가능합니다. 삽입이 빠르기 때문에 들어오는 이벤트 또는 데이터를 처리하고 항상 가장 빠르고 가장 큰 데이터에 액세스 할 수있는 좋은 방법입니다.
우선 순위 대기열, 스케줄러 (가장 빠른 항목이 필요한 경우) 등에 유용합니다.
힙은 상위 노드의 값이 하위 노드의 값보다 큰 트리입니다.
힙을 깊이에 따라 선형 순서로 저장된 이진 트리로 생각하면 루트 노드가 먼저 (그런 다음 해당 노드의 하위가 다음으로 해당 노드의 하위가 다음)됩니다. 그러면 인덱스 N에있는 노드의 자식은 2N + 1과 2N + 2에 있습니다. 이 속성을 사용하면 인덱스별로 빠르게 액세스 할 수 있습니다. 그리고 힙은 노드를 교체하여 조작되기 때문에 내부 정렬이 가능합니다.
힙은 최소값 또는 최대 값에 빠르게 액세스 할 수있는 구조 입니다.
하지만 왜 그걸 원하겠습니까? 추가시 모든 항목을 확인 하여 가장 작은 지 또는 가장 큰지 확인할 수 있습니다. 이렇게하면 항상 일정한 시간에 가장 작거나 가장 큰 것을 갖게됩니다 O(1).
대답은 힙을 사용하면 가장 작은 또는 가장 큰 것을 가져오고 NEXT 가장 작은 또는 가장 큰 것을 빠르게 알 수 있기 때문 입니다. 이것이 우선 순위 대기열이라고하는 이유입니다.
실제 세계의 예 (그다지 공정하지 않은 세계) :
나이에 따라 환자가 진료를받는 병원이 있다고 가정 해 보겠습니다. 가장 오래된 사람이 대기열에 언제 들어 갔는지에 관계없이 항상 먼저 참석합니다.
가장 오래된 것을 추적 할 수는 없습니다. 그 / 그녀를 꺼내면 다음으로 가장 오래된 것을 알 수 없기 때문입니다. 이 병원 문제를 해결하기 위해 max heap 을 구현합니다 . 이 힙은 정의에 따라 부분적으로 정렬됩니다. 즉, 환자를 나이별로 분류 할 수는 없지만 가장 오래된 환자가 항상 맨 위에 있다는 것을 알고 있으므로 환자를 일정한 시간에 꺼내고 O(1)로그 시간에 힙 균형을 다시 조정할 수 있습니다 O(log N).
더 정교한 예 :
일련의 정수가 있고 median. 중앙값은 정렬 된 배열의 중간에있는 숫자입니다.
예:
[1, 2, 5, 7, 23, 27, 31]
위의 경우 7더 작은 숫자를 포함하는 배열 [1, 2, 5]은 더 큰 숫자를 포함하는 배열 과 크기가 같으 므로 중앙값 입니다 [23, 27, 31]. 일반적으로 배열에 짝수의 요소가있는 경우 중앙값은 중간에있는 두 요소의 산술 평균입니다 (예 :) (5 + 7)/2.
이제 중앙값을 어떻게 추적합니까? 2 개의 힙을 가짐 으로써 현재 중앙값보다 작은 숫자를 포함하는 최소 힙 하나와 현재 중앙값보다 큰 숫자를 포함하는 최대 힙. 이제 이러한 힙이 항상 균형을 이루는 경우 2 개의 힙은 동일한 수의 요소를 포함하거나 하나는 다른 하나보다 1 개의 요소를 더 많이 포함합니다.
시퀀스에 새 요소를 추가 할 때 숫자가 현재 중앙값보다 작 으면 최소 힙에 추가하고, 그렇지 않으면 최대 힙에 추가합니다. 힙이 (하나의 힙이 더 다른 것보다 1 개 이상의 요소가) 불균형이 있다면 이제, 당신은 당기 가장 큰 힙에서 요소 및 추가 작은에. 이제 균형이 잡혔습니다.
힙의 특징은 데이터를 반순으로 유지하는 구조라는 것입니다. 따라서 완전한 질서를 유지하는 비용과 무작위 혼돈을 통한 탐색 비용 사이의 좋은 절충안입니다. 이 특성은 선택, 정렬 또는 분류와 같은 많은 알고리즘에서 사용됩니다.
힙의 또 다른 유용한 특성은 배열에서 제자리에 만들 수 있다는 것입니다!
선택 알고리즘 (최소 또는 최대 찾기)에도 좋습니다.
임시 목록을 정렬 할 때 언제든지 힙을 고려해야합니다.
가장 작은 요소와 가장 큰 요소에 각각 액세스하려는 경우 minHeap 또는 maxHeap을 사용할 수 있습니다.
참고 URL : https://stackoverflow.com/questions/749199/when-would-i-want-to-use-a-heap
'developer tip' 카테고리의 다른 글
| PIL을 사용하여 이미지에 텍스트 추가 (0) | 2020.10.07 |
|---|---|
| VB.NET에서 클래스를 정적으로 표시 (0) | 2020.10.07 |
| .NET DLL에 git 커밋 해시 포함 (0) | 2020.10.07 |
| ES6로 두 개체 병합 (0) | 2020.10.07 |
| 왜 'd / = d'는 d == 0 일 때 0으로 나누기 예외를 발생시키지 않습니까? (0) | 2020.10.07 |