aalhour/C-Sharp-Algorithms

MaxHeap bad algorithm.

Open

#84 opened on Dec 28, 2018

View on GitHub
 (2 comments) (0 reactions) (0 assignees)C# (5,736 stars) (1,409 forks)batch import
buggood first issue

Description

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.

Contributor guide

Tech stack
csharp
Domain
dataperformance
Issue type
bug
DifficultyEstimated implementation difficulty for a new contributor, from 1 for very small changes to 5 for expert-level work.
3
Estimated timeA rough time range for an experienced contributor to investigate, implement, test, and prepare a pull request.
1-3 hours
Activity statusHow available the issue appears right now: fresh, active, stale, blocked, or waiting on maintainer input.
stale
ClarityHow clearly the issue explains the expected change, acceptance criteria, and next step.
mostly clear
Prerequisites
C# basicsunderstanding of heap data structure
Newbie friendlinessA 1-100 score estimating how approachable this issue is for first-time contributors.
40
Research direction
Examine the MaxHeap implementation in the repository (likely in DataStructures/Heaps/MaxHeap.cs). Compare its insert and extract operations with a standard O(log n) binary heap. The inefficient algorithm might be using linear scans (e.g., for finding parent/child indices or for rebalancing). Check for unnecessary loops or recursive calls that cause O(n) complexity. Look at the linked BinaryHeap from Algorithmia for reference.