C++ 힙을 내려 놓습니다.

저는 힙을 사용해야하는 프로그램을 작성하고 있으며 모든 정렬 방법 외에도 모든 것이 잘 작동합니다! 나는 내 논리가 무엇이 잘못되었거나 어리석은 뭔가를 놓치고 있는지 확신하지 못한다. 그러나 이것을 보아주는 눈의 신선한 세트는 좋을 것입니다.C++ 힙을 내려 놓습니다.

함수는 물론 힙, 루트의 위치, 그리고 STL보다 작거나 큰 술어 인 내 벡터를 전달합니다.

template<class T,class P> 
void upheap(vector<T>& v, int start, P func) { 
    T x = v[start]; 
    while (start > 1 && func(x, v[start/2])) { 
     v[start] = v[start/2]; start /= 2; 
    } 
    v[start] = x; 
}

어떤 아이디어가 잘못 되었나요?

출처

2010-12-03 rajh2504

힙의 루트를 지나가고 있다고 말할까요? 열혈해야하는 요소의 인덱스를 전달하면 안됩니까? –

죄송합니다. 그게 인덱스 값이었던 것입니다. – rajh2504

어쩌면 불변량, 선행 조건 및 사후 조건을 작성해야합니다. 그러면 문제가 나타날 것입니다. 예를 들어, 입력시 'HEAP (i = 0 .. start-1)'조건이 true입니까? 그리고 나서 목표는 'HEAP (i = 0..start)'조건을 종료 할 때 true로 설정하는 것입니다. –

벡터의 첫 번째 요소는 v [0]입니다. 당신은 그것이 [1]에 있다고 가정하는 것 같습니다. 이것에 대한 이유가 있습니까?

인덱스 i에 노드가있는 경우 루트가 v [0]에 있으면 부모는 int ((i-1)/2)입니다 (그러나 (i-1) >> 1이 더 효율적일 수 있음) , 아이들은 2i + 1, 2i + 2에 있습니다. 예 : 루트 V에 있으면 한편

 0 
    1 2 
3 4 5 6 
78 9A BC DE

은, [1], 부모 (I/2) (I 또는 >> 1) 어린이 2I에 있으며, 2I INT 있어요 +1. 예 :

 1 
    2 3 
4 5 6 7 
89 AB CD EF

그래서 문제가 될 수 있습니다.

func (x, v [시작/2])이 맞는지 확인하십시오. 만약 func이 힙 조건이라면, 그것이 거짓인지 체크 할 수 있습니다 ...

벡터가 이미 v [start]를 포함 할만큼 충분히 큰가요? upheap()이 힙에 항목을 한 번에 하나씩 추가하는 데 사용되는 경우 ... 벡터의 크기가 증가하지 않습니다 ... (또한 v [1]이 아닌 v [0]에서 시작합니다. 그래서 그 여분의 요소입니다.) 힙을 인쇄하여 루프에 추가하고 실행하기위한 간단한 스캐 폴딩 (테스트/디버깅에는 사용되지만 최종 제품에는 포함되지 않음) 루틴을 작성해 보았습니까? 일들이 어디에서 벗어날지를 알기위한 연습 데이터?

출처

2010-12-03 05:32:25

C++ 힙을 내려 놓습니다.

답변

관련 문제