[C++ Fundamentals of Data Structures/C++ 자료구조론(이석호)] 5.6 히프 연습문제

2. 

<최소 히프에서의 삽입>

void MinHeap<T> ::: Push(const T& e) {
	if(heapSize == capacity) {
    	Change1D(heap, capacity, 2*capacity);
        capacity *= 2;
    }
    int currentNode = ++heapSize; //데이터가 들어갈 위치 : heapSize + 1
    while (currentNode !=1 && heap[currentNode/2] > e) {
    	heap[currentNode] = heap[currentNode/2];
        currentNode /= 2;
    }
    heap[currentNode] = e;
}

 

<최소 히프에서의 삭제>

void MinHeap<T> :: Pop() {
	if(IsEmpty()) throw "Heap is empty.";
    heap[1]. ~T(); //최대 원소 제거
    T lastE = heap[heapSize --]; //히프의 마지막 원소 제거(lastE에 히프 마지막 원소 저장)
    int currentNode = 1; // 루트
    int child = 2; //currentNode의 자식노드
    while (child <= heapSize) {
    	if(child < heapSize && heap[child] > heap[child+1])
        	child ++;
        if(lastE <= heap[child])
        	break;
        heap[currentNode] = heap[child];
        currentNode = child;
        child *= 2;
    }
    heap[currentNode] = lastE;
}