Maximum Binary Heap Removal

[Kourosh23]

I have a maximum binary heap implemented as a priority queue. The below code works fine.

I need some clarification to know if my remove function is doing O(log n) work? If yes, how do you know? If no, could you please explain why?

Thanks :)

template <class T>
void priorityQueue<T>::heapDown(int i)
{
    int l = leftChild(i);
    int r = rightChild(i);
    int x = 0;
    int n = size();

    if (l < n && arr[i] < arr[l])
    {
        x = l;
        if (r < n && arr[l] < arr[r])
            x = r;
    }

    else if (r < n && arr[i] < arr[r])
        x = r;

    if (x != 0)
    {
    	T temp = arr[x];
    	arr[x] = arr[i];
    	arr[i] = temp;
        heapDown(x);
    }
}

template<class T>
void priorityQueue<T>::heapify(T arr[], int size){
	int i = (size)/2;		
	while(i >= 0){
		heapDown(i);
		i -= 1;
	}
}


template<class T>
T priorityQueue<T>::remove(){
	if(size() == 0){
		throw runtime_error("Warning: size < 0");
	}
	
	T highestPriority = arr[i];

	int indexOfRoot = 0;
        arr[indexOfRoot] = arr[size()-1];    // size() returns the num of elements in the array
        currentSize -=1;

        reheapDown(indexOfRoot);     // or heapify(arr, size()) ???
        // heapify(arr, size());   // ???


	return highestPriority;
}

[Kourosh23]

I am still looking for suggestions and explanations, and I am open to discussion as well :)

[Kourosh23]

I figured out the answer to my question, and I decided to share it here.

If you call heapify(arr, size()), it will actually cause output errors, and I managed to realize this issue during my testing process.

It is better to call reheapDown(0), 0 indicating the index of the root. If you do this, the remove function will always remove an element at O(log n) time complexity.

There might be other ways to implement this, but I figured out my method results in the right output by testing my remove function multiple times, and my max heap array was able to keep its maximum heap property after each removal until size() resulted in 0.

I hope this helps someone in the future.