알고리즘 도론 제6장
4976 단어 알고리즘 도론
1 HEAP-MINIMUM(A)
2 return A[1]
3
4 HEAP-EXTRACT-MIN(A)
5 if A.heap-size < 1
6 error "heap underflow"
7 min = A[1]
8 A[1] = A[A.heap-size]
9 A.heap-size = A.heap-size - 1
10 MIN-HEAPIFY(A, 1)
11 return min
12
13 HEAP-DECREASE-KEY(A, i, key)
14 if key > A[i]
15 error "new key is biger than current key"
16 A[i] = key
17 while i < A.heap-size and A[PARENT(i)] > A[i]
18 exchange A[i] and A[PARENT(i)]
19 i = PARENT(i)
20
21 MIN-HEAP-INSERT(A, key)
22 A.heap-size = A.heap-size + 1
23 A[A.heap-size] = INT_MAX
24 HEAP-DECREASE-KEY(A, A.heap-size, key)6.5-6
해답: 제목에서 변수 A[i]와 A[PARENT(i)]를 교환하여 실현합니다.정렬을 삽입하는 방법을 참고하여 A[i] = A[PARENT(i)]를 A[PARENT(i)] > A[i]까지 한 다음 i에 키워드를 삽입합니다.
6.5-7
대기열의 실현: 입대 시간을 키워드로 최소 우선 대기열 만들기
창고의 실현: 입대 시간을 키워드로 최대 우선 대기열 만들기
6.5-8
최대 더미라고 가정하고 키워드 A[i]를 삭제한 후 더미의 구조성을 유지하기 위해 A[A.heap-size]를 A[i] 대신 선택한다.
1. 대체할 경우 A[i]
1 Input: A max-heap and an integers i
2 Output: The heap A with element a position i delete
3
4 A[i] = A[A.heap-size]
5 A.heap-size = A.heap-size - 1
6 key = A[i]
7 if key <= A[PARENT(i)]
8 MAX-HEAPIFY(A, i)
9 else
10 while i > 1 and A.[PARENT(i)] < key
11 A[i] = A[PARENT(i)]
12 i = PARENT(i)
13 A[i] = key6.5-9
답변:
1. k개의 체인 테이블의 첫 번째 요소를 최소 더미에 넣는 것을 선택한다
2. 더미 속의 최소 원소를 정렬된 표에 넣고 최소 원소가 있는 체인 표에서 다음 원소를 선택하여 최소 더미에 넣는다
3. 정렬이 완료될 때까지 반복
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
알고리즘 도론 활동 선택 문제텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
