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.
<rt id="pwjBlLZ"><small id="pwjBlLZ"></small></rt>
<acronym id="pwjBlLZ"></acronym><rt id="pwjBlLZ"></rt>
<tr id="pwjBlLZ"><optgroup id="pwjBlLZ"></optgroup></tr><tr id="pwjBlLZ"><optgroup id="pwjBlLZ"></optgroup></tr><acronym id="pwjBlLZ"><small id="pwjBlLZ"></small></acronym>
<acronym id="pwjBlLZ"><optgroup id="pwjBlLZ"></optgroup></acronym>
<option id="pwjBlLZ"></option>
<tr id="pwjBlLZ"><optgroup id="pwjBlLZ"></optgroup></tr>
<acronym id="pwjBlLZ"><small id="pwjBlLZ"></small></acronym><acronym id="pwjBlLZ"></acronym>
<acronym id="pwjBlLZ"><small id="pwjBlLZ"></small></acronym>
  • 6512882421 2018-04-19
  • 4659652420 2018-04-19
  • 2967832419 2018-04-19
  • 8339042418 2018-04-19
  • 8147112417 2018-04-19
  • 2774752416 2018-04-19
  • 4316132415 2018-04-19
  • 6265742414 2018-04-19
  • 1875142413 2018-04-19
  • 4146552412 2018-04-19
  • 8205662411 2018-04-19
  • 959982410 2018-04-19
  • 7153742409 2018-04-19
  • 9349932408 2018-04-18
  • 6024052407 2018-04-18
  • 2113432406 2018-04-18
  • 7629172405 2018-04-18
  • 163882404 2018-04-18
  • 3515922403 2018-04-18
  • 5047802402 2018-04-18