MaxHeap bad algorithm.

[crucialize]

steps to reproduce

Write a loop, from 1 to 80000, each time add a random int to the max heap.

In theory it takes very little time(NlogN, N=80000, <1sec ), but the program does take a long time.

I'v also tested the BinaryHeap in https://github.com/SolutionsDesign/Algorithmia, it performs well, so it is probably due to the bad algorithm.

[aalhour]

@crucialize - would you like to submit a PR for this?

[davidsonbrsilva]

Good afternoon! So, I've tested the BinaryMaxHeap class according the steps above and here the execution was perfect. For testing, I've created a execution project with a Main Class program with the follow code:

BinaryMaxHeap<long> maxHeap = new MaxHeap<long>(Comparer<long>.Default);
Random rand = new Random();

/* Adding the elements to heap. */
for (int i = 0; i < 80000; ++i)
{
    maxHeap.Add(rand.Next());
}

/* Removing the elements from heap. */
while (!maxHeap.IsEmpty)
{
    var element = maxHeap.ExtractMax();

    /* Showing part of heap. */
    if (maxHeap.Count % 2000 == 0)
    {
        Console.WriteLine(element);
    }
}

Maybe the found problem is related to execution time to generate random numbers, it's my guess. If a random object is created each time a random number is generated, putting the instantiation line inside loop affects performance.

Hope this helps!