기술나눔

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

더미

힙 및 우선순위 큐:

우선순위 큐는 추상 데이터 유형이고 힙은 데이터 구조이므로 힙은 우선순위 큐를 구현하는 방법이 아닙니다.
배열, 연결리스트 등 우선순위 큐를 구현하는 방법에는 여러 가지가 있습니다. 그러나 이러한 구현에서는 삽입 및 삭제 작업 중 하나가 O(1)O(1) 시간 복잡도로 완료될 수 있고 다른 작업은 O(N)O(N) 시간 복잡도로 완료되어야 한다는 것만 보장할 수 있습니다. 시간 복잡도. 힙은 O(log N)O(logN)의 시간 복잡도 내에 우선순위 큐의 삽입 작업이 완료되고, O(log N)O(logN)의 시간 복잡도 내에 삭제 작업이 완료되도록 할 수 있다. .

힙은 다음 조건을 충족하는 특수 이진 트리입니다.

1. 완전한 이진 트리(노드가 왼쪽에서 오른쪽으로 순서대로 배치됨)
2. 각 노드의 값은 해당 하위 노드의 값보다 크거나 같거나 작거나 같아야 합니다.

힙의 특징:

1. 요소는 O(logN) 시간 복잡도로 힙에 삽입될 수 있습니다.
2. 요소는 O(logN) 시간 복잡도로 힙에서 삭제될 수 있습니다.
3. 힙의 최대값 또는 최소값은 O(1) 시간 복잡도 내에서 얻을 수 있습니다.

힙 분류:

최대 힙: 힙에 있는 각 노드의 값은 해당 하위 노드의 값보다 크거나 같습니다. 최대 힙의 최상위 요소(루트 노드)는 힙의 최대값입니다.
최소 힙: 힙에 있는 각 노드의 값은 해당 하위 노드의 값보다 작거나 같습니다. 최소 힙의 최상위 요소(루트 노드)는 힙의 최소값입니다.
현재 노드 번호는 i이고, 왼쪽 자식의 번호는 2i, 오른쪽 자식의 번호는 2i+1이다.

시간복잡도와 공간복잡도

힙 정렬

이론: 힙 정렬은 힙의 데이터 구조를 사용하여 정렬되지 않은 요소 집합을 정렬하는 것을 의미합니다.

최소 힙 정렬 알고리즘의 단계는 다음과 같습니다.

모든 요소를 ​​최소 힙으로 힙합니다.
힙의 최상위 요소를 꺼내 삭제하고 순서가 지정된 요소를 저장하는 데이터 세트 T에 힙의 최상위 요소를 배치합니다.
이때 힙은 새로운 최소 힙으로 조정됩니다.
힙에 요소가 없어질 때까지 3단계와 4단계를 반복합니다.
이 시점에서 작은 것부터 큰 것 순으로 배열된 새로운 데이터 세트 T가 획득된다.

최대 힙 정렬 알고리즘의 단계는 다음과 같습니다.

모든 요소를 ​​최대 힙으로 힙합니다.
힙의 최상위 요소를 꺼내 삭제하고 순서가 지정된 요소를 저장하는 데이터 세트 T에 힙의 최상위 요소를 배치합니다.
이때 힙은 새로운 최대 힙으로 조정됩니다.
힙에 요소가 없어질 때까지 3단계와 4단계를 반복합니다.
이 시점에서, 요소들이 큰 것부터 작은 것 순으로 배열된 새로운 데이터 세트 T가 획득된다.
시간 복잡도: O(Nlog N). N은 힙의 요소 수입니다.

공간 복잡도: O(N). N은 힙의 요소 수입니다.