Maximum Binary Heap Removal

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 :)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

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;
}

Last edited on
I am still looking for suggestions and explanations, and I am open to discussion as well :)
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.



Registered users can post here. Sign in or register to post.
  • 1007451581 2018-02-22
  • 8908121580 2018-02-22
  • 141161579 2018-02-22
  • 9421578 2018-02-22
  • 2826901577 2018-02-22
  • 3647361576 2018-02-22
  • 5717551575 2018-02-22
  • 523811574 2018-02-22
  • 6439871573 2018-02-22
  • 8109431572 2018-02-22
  • 8757321571 2018-02-22
  • 5265111570 2018-02-22
  • 3351351569 2018-02-22
  • 5109361568 2018-02-22
  • 4455391567 2018-02-22
  • 9091121566 2018-02-22
  • 24791565 2018-02-22
  • 2486841564 2018-02-21
  • 9847231563 2018-02-21
  • 9264681562 2018-02-21