HeapShit

    interface SomeData
    {
        void Push(long element);
        long Pop();
        long GetMax();
        void RemoveMax();
    }

    public class StupidDatum
    {
        public long value;
        public int heapIndex = -1;
        public LinkedListNode<StupidDatum> listNode;

        public StupidDatum(long value)
        {
            this.value = value;
            listNode = new LinkedListNode<StupidDatum>(this);
        }
    }
    public static class HeapTests
    {
        [Test]
        public static void IsHeapish()
        {
            List<long> data = new List<long>();
            int curValue = 234246233;

            for (int ix = 0; ix < 100; ix++)
            {
                curValue = curValue * 1345378247;
                data.Add(curValue);
            }

            StupidHeap heap = new StupidHeap(data.Count);
            data.Select(x => new StupidDatum(x)).ToList().ForEach(heap.Add);

            data.Sort();
            data.Reverse();

            while(data.Count > 0)
            {
                Assert.AreEqual(data.First(), heap.GetMax());
                if(0 != heap.MaxObj().heapIndex)
                {
                    Assert.AreEqual(0, heap.MaxObj().heapIndex);
                }
                data.RemoveAt(0);
                heap.RemoveMax();
            }
        }
    }
    public class StupidHeap
    {
        int endIndex = 0;
        StupidDatum[] buffer;

        static int[] levelStarts;
        static StupidHeap()
        {
            List<int> levelStarts = new List<int>();

            long maxSize = long.MaxValue;

            int count = 1;
            int pos = 0;
            while (maxSize > 0)
            {
                levelStarts.Add(pos);
                maxSize -= count;
                pos += count;
                count *= 2;
            }

            StupidHeap.levelStarts = levelStarts.ToArray();
        }

        public StupidHeap() { }
        public StupidHeap(int maxSize)
        {
            buffer = new StupidDatum[maxSize];
        }

        public StupidDatum MaxObj()
        {
            return buffer[0];
        }

        public long GetMax()
        {
            if (endIndex == 0) return long.MinValue;
            return buffer[0].value;
        }
        public void Add(StupidDatum value)
        {
            value.heapIndex = endIndex;
            buffer[endIndex++] = value;

            BubbleUp(endIndex - 1);
        }

        [Test]
        [TestCase(0, ExpectedResult = 0)]
        [TestCase(1, ExpectedResult = 1)]
        [TestCase(2, ExpectedResult = 1)]
        [TestCase(3, ExpectedResult = 2)]
        [TestCase(14, ExpectedResult = 3)]
        [TestCase(15, ExpectedResult = 4)]
        public static int Level(int index)
        {
            int level = 0;
            while(index >= levelStarts[level])
            {
                level++;
            }
            return level - 1;
        }
        [Test]
        [TestCase(0, ExpectedResult = 0)]
        [TestCase(2, ExpectedResult = 0)]
        [TestCase(5, ExpectedResult = 2)]
        [TestCase(6, ExpectedResult = 2)]
        [TestCase(7, ExpectedResult = 3)]
        [TestCase(11, ExpectedResult = 5)]
        [TestCase(14, ExpectedResult = 6)]
        public static int Parent(int index)
        {
            if (index == 0) return 0;

            int level = Level(index);

            int start = levelStarts[level];
            int prevStart = levelStarts[level - 1];

            return prevStart + (index - start) / 2;
        }
        [Test]
        [TestCase(0, ExpectedResult = 1)]
        [TestCase(1, ExpectedResult = 3)]
        [TestCase(2, ExpectedResult = 5)]
        [TestCase(3, ExpectedResult = 7)]
        [TestCase(4, ExpectedResult = 9)]
        [TestCase(5, ExpectedResult = 11)]
        [TestCase(6, ExpectedResult = 13)]
        public static int LeftChild(int index)
        {
            int level = Level(index);

            int start = levelStarts[level];
            int nextStart = levelStarts[level + 1];

            return nextStart + (index - start) * 2;
        }
        public static int RightChild(int index)
        {
            return LeftChild(index) + 1;
        }
        public void RemoveMax()
        {
            Remove(0);
        }
        public void Remove(int index)
        {
            buffer[index] = buffer[--endIndex];
            buffer[index].heapIndex = index;

            index = BubbleUp(index);
            BubbleDown(index);
        }
        private void BubbleDown(int index)
        {
            var ourObj = buffer[index];
            long ourVal = buffer[index].value;

            while (true)
            {
                long leftValue = ourVal;
                long rightVal = ourVal;

                int leftIndex = LeftChild(index);
                if (leftIndex < endIndex)
                {
                    leftValue = buffer[leftIndex].value;
                }
                int rightIndex = RightChild(index);
                if (rightIndex < endIndex)
                {
                    rightVal = buffer[rightIndex].value;
                }

                if (ourVal >= leftValue && ourVal >= rightVal) return;

                bool leftSide = ourVal < leftValue;
                if (ourVal < rightVal && rightVal > leftValue)
                {
                    leftSide = false;
                }

                if (leftSide)
                {
                    buffer[index] = buffer[leftIndex];
                    buffer[index].heapIndex = index;
                    buffer[leftIndex] = ourObj;
                    index = leftIndex;
                }
                else
                {
                    buffer[index] = buffer[rightIndex];
                    buffer[index].heapIndex = index;
                    buffer[rightIndex] = ourObj;
                    index = rightIndex;
                }

                ourObj.heapIndex = index;
            }
        }
        private int BubbleUp(int index)
        {
            var val = buffer[index];
            long value = val.value;

            while (index != 0)
            {
                int parentIndex = Parent(index);
                StupidDatum parVal = buffer[parentIndex];
                if (value <= parVal.value) break;
                //Swap with parent and continue
                buffer[index] = parVal; parVal.heapIndex = index;
                buffer[parentIndex] = val; val.heapIndex = parentIndex;
                index = parentIndex;
            }
            return index;
        }
    }

    public static class LinkedImplTests
    {
        [Test]
        public static void FuckThis()
        {
            LinkedImpl test = new LinkedImpl(100);
            test.Push(5);
            test.Push(6);
            test.Push(7);
            test.Push(4);
            test.Push(2);

            Assert.AreEqual(7, test.GetMax());
            test.RemoveMax();
            Assert.AreEqual(6, test.GetMax());

            test.Push(10);
            test.Push(1);
            Assert.AreEqual(10, test.GetMax());
            test.Pop();
            Assert.AreEqual(10, test.GetMax());
            test.Pop();
            Assert.AreEqual(6, test.GetMax());

            test.Pop();
            test.Pop();
            test.Pop();
            test.Pop();
            Assert.AreEqual(5, test.GetMax());
        }
    }

    public class LinkedImpl : SomeData
    {
        private LinkedList<StupidDatum> linkedList = new LinkedList<StupidDatum>();
        private StupidHeap heap;

        public LinkedImpl(int maxElems)
        {
            heap = new StupidHeap(maxElems);
        }

        public void Push(long element)
        {
            StupidDatum elem = new StupidDatum(element);

            linkedList.AddLast(elem.listNode);
            heap.Add(elem);
        }

        public long Pop()
        {
            var val = linkedList.Last;

            heap.Remove(val.Value.heapIndex);
            linkedList.Remove(val);

            return val.Value.value;
        }

        public long GetMax()
        {
            var val = heap.MaxObj();
            if (val == null) return long.MinValue;
            return val.value;
        }

        public void RemoveMax()
        {
            var val = heap.MaxObj();
            if (val == null) return;

            heap.Remove(val.heapIndex);
            linkedList.Remove(val.listNode);
        }
    }