CareerCup

Implement a min heap of 1 million numbers

@deep0mal
what do you mean by 'track' ?
it could mean: count occurrence, find smallest/largest/median/average ...

void findLargest(int* const dataSet,const int dataSetSize,const int numLargest)
{
    vector<int> heap;
    for(int dataIndex = 0; dataIndex < dataSetSize; ++dataIndex)
    {
        const int nextInt = dataSet[dataIndex];
        if(heap.size() < numLargest)
        {
            heap.push_back(nextInt);
            push_heap(heap.begin(),heap.end(),greater<int>());
        }
        else
        {
            int heapMin = heap.front();
            if(nextInt > heapMin)
            {
                pop_heap(heap.begin(),heap.end(),greater<int>());
                heap.pop_back();
                
                heap.push_back(nextInt);
                push_heap(heap.begin(),heap.end(),greater<int>());
            }
        }
    }
    
    for(vector<int>::const_iterator it = heap.begin(); it != heap.end(); ++it)
    {
        printf("%d ",*it);
    }
    printf("\n");
}

Just implement a min-heap with 1 million of size.
In any time in the heap you will have the first million of max numbers

private class Heap
		{
			private int[] array;

			private int currentSize = 0;

			public Heap(int size)
			{
				this.array = new int[size];
				this.currentSize = 0;
			}

			public bool IsFull
			{
				get
				{
					return this.currentSize == array.Length;
				}
			}

			private void Swap(int first, int second)
			{
				int tmp = array[first];
				array[first] = array[second];
				array[second] = tmp;
			}

			public bool Insert(int value)
			{
				if (!IsFull)
				{
					array[currentSize++] = value;
					HeapifyUp(currentSize - 1);
					return true;
				}

				return false;
			}

			public void HeapifyUp(int curr)
			{
				while (curr != 0)
				{
					int parent = curr % 2 == 0 ? (curr >> 1) - 1 : curr >> 1;

					if (array[curr] < array[parent])
					{
						Swap(curr, parent);
						curr = parent;
					}
					else
					{
						return;
					}
				}
			}

			public int GetRoot()
			{
				if (currentSize > 0)
				{
					return array[0];
				}

				throw new Exception("Heap is empty");
			}

			public void UpdateRoot(int value)
			{
				if (currentSize > 0)
				{
					array[0] = value;
					HeapifyDown(0);
				}
			}

			public void HeapifyDown(int curr)
			{
				while (true)
				{
					int left = (curr << 1) + 1;
					int right = (curr << 1) + 2;

					if (left >= currentSize)
					{
						break;
					}

					int optimal = left;

					if (right < currentSize && array[right] < array[left])
					{
						optimal = right;
					}

					if (array[curr] > array[optimal])
					{
						Swap(curr, optimal);
						curr = optimal;
					}
					else
					{
						break;
					}
				}
			}
		}

		public void ProcessNumbers(IEnumerable<int> numbers)
		{
			Heap h = new Heap(5);

			foreach (int number in numbers)
			{
				if (!h.IsFull)
				{
					h.Insert(number);
				}
				else
				{
					int min = h.GetRoot(); // it will be the minimum value of heap
					if (number > min)
					{
						h.UpdateRoot(number);
					}
				}
			}
		}