c# - 堆的性能低下。 O(n) 而不是 O(log n)

Question

我遇到堆性能问题。我不知道我的代码的哪一部分会影响这个数据结构的性能。例如插入/删除 9999 个元素需要 12000 毫秒。堆必须在 100 毫秒内完成(理论上)。正常列表在 20000 毫秒内就完成了。您能指出我在代码中使用的一些坏习惯吗？

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class Heap
    {
        int[] items;
        int size = 1;
        public Heap()
        {
            items = new int[size]; 
        }
        public Heap(int size)
        {
            items = new int[size];
        }
        public void AddOnLast(int value)
    {
        int i = items.Length + 1;
        Array.Resize(ref items, i);
        items[items.Length-1] = value;
    }
    // Deleting item of specific index from the array/ using LINQ
    public void RemoveAt(int indexToRemove)
    {
         items = items.Where((source, indexOfElements) => indexOfElements != indexToRemove).ToArray();
    }
    /*Method which push up the elment after adding it on the last place
    k - last index/ when k=0, element is on the top of the heap
    p - parent index/ item - value of element/ parent - value of parent */
    private void PushUp()
    {
        int k = items.Length - 1;
        while (k > 0)
        {
            int p = (k - 1) / 2;
            int item = items[k];
            int parent = items[p];
            if (item > parent)
            {
                //Swap of elements
                items[k] = parent;
                items[p] = item;
                k = p;
            }
            else
            {
                break;
            }
        }
    }

    // Method which put element in correct place of the heap
    public void insert(int value)
    {
        AddOnLast(value);
        PushUp();
    }

    /* After deleting item from the heap we have to push down element to check if heap structure is correct
    k - index of first element, top of the heap/ l - left "child" index / r - right child index
    max is max value - either right or left child  */
    private void PushDown()
    {
        int k = 0;
        int l = 2 * k + 1;
        while (l < items.Length)
        {
            int max = 1;
            int r = l + 1;
            if (r < items.Length)
            {
                if (items[r] > items[l])
                {
                    //max become right child
                    max++;
                }
            }
            if (items[k] < items[max])
            {
                //swap of 2 values, prevous element and next element are swapped
                int temp = items[k];
                items[k] = items[max];
                items[max] = temp;
            }
            else
            {
                break;
            }
        }
    }

    //Deleting item from the top of the heap
    public void delete()
    {
            if (items.Length == 0)
            {
                Console.Write("No elements to delete");
            }
               else if (items.Length == 1)
                {
                    RemoveAt(0);
                }
                else
                {
                    int hold = items[0];// we hold the first element
                items[0] = items[items.Length - 1]; // last element become first
                RemoveAt(items.Length - 1); // we delete last element, and check if last element which is now on the top of the heap is on the right place
                PushDown();
                }  
    }

}

Answer 1

您的代码实际上存在比速度更严重的问题(这是由每次插入时调整数组大小引起的)。

• RemoveAt - 您的实现破坏了堆。您应该从末尾插入项目并下推/上推它。除此之外，人们怎么知道要删除的索引？
• 下推不起作用，您不更改变量“l”。而且您使用“max”索引的方式不正确。
• 删除可以，但是您没有提供获取该值的选项。而是从流行音乐开始。
• 公共(public) AddOnLast 的目的是什么？您不应该提供破坏堆的方法。
• 没有参数检查只是一个细节

看看这个

class Heap
        {
            int[] items;
            int size = 0;
            public Heap() : this(16)
            {
            }
            public Heap(int initSize)
            {
                if (initSize < 1)
                {
                    throw new ArgumentException("Size must be greater than 0");
                }
                items = new int[initSize];
            }


            /*Method which push up the elment after adding it on the last place
            k - last index/ when k=0, element is on the top of the heap
            p - parent index/ item - value of element/ parent - value of parent */
            private void PushUp()
            {
                int k = size - 1;
                while (k > 0)
                {
                    int p = (k - 1) / 2;
                    int item = items[k];
                    int parent = items[p];
                    if (item > parent)
                    {
                        //Swap of elements
                        items[k] = parent;
                        items[p] = item;
                        k = p;
                    }
                    else
                    {
                        break;
                    }
                }
            }

            // Method which put element in correct place of the heap
            public void Insert(int value)
            {
                if (items.Length <= size)
                {
                    Array.Resize(ref items, items.Length * 2);
                }
                items[size++] = value;
                PushUp();
            }

            public bool IsEmpty()
            {
                return size == 0;
            }

            /* After deleting item from the heap we have to push down element to check if heap structure is correct
            k - index of first element, top of the heap/ l - left "child" index / r - right child index
            max is max value - either right or left child  */
            private void PushDown(int k)
            {
                int l = 2 * k + 1;
                while (l < size)
                {
                    int max = l;
                    int r = l + 1;
                    if (r < size)
                    {
                        if (items[r] > items[l])
                        {
                            //max become right child
                            max = r;
                        }
                    }
                    if (items[k] < items[max])
                    {
                        //swap of 2 values, prevous element and next element are swapped
                        int temp = items[k];
                        items[k] = items[max];
                        items[max] = temp;
                    }
                    else
                    {
                        break;
                    }
                    k = max;
                    l = 2 * k + 1;
                }
            }

            //Deleting item from the top of the heap
            public int Pop()
            {
                if (size == 0)
                {
                    throw new DataException("No elements to delete");
                }
                else if (size == 1)
                {
                    return items[--size];
                }
                else
                {
                    int ret = items[0];
                    items[0] = items[--size];
                    PushDown(0);
                    return ret;
                }
            }
        }