堆性能低下。 O（n）而不是\t O（日志n）

Question

我有一堆性能问题。我不知道我的代码的哪一部分会影响这个数据结构的性能。例如插入/删除9999个元素需要12000毫秒。堆必须在100ms内完成（理论上）。普通列表在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 - 您的实施打破了堆。您应该从最后插入项目并PushDown/PushUp它。除此之外，任何人应该如何知道索引要删除？
• PushDown不起作用，您不会更改变量“l”。你使用“最大”索引的方式是不正确的。
• 删除是好的，但你没有选择获得该值。而是从Pop开始。
• 公共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; 
       } 
      } 
     } 

Answer 2

几件事情，也许有低性能：

Array.Resize 
Your implementation of RemoveAt 
Your implementation of insert 

不知道我理解你需要达到的目标，但似乎你可以用一个简单的List<int>

RemoveAt -> List.RemoveAt 
AddOnLast -> List.Add 
Insert-> List.Insert(0, yourValue) //(If I understand correctly what you need) 
delete -> List.removeAt(0) // or maybe List.removeAt(list.Length - 1) 

取代你堆类

我相信Microsoft（和Mono编码人员）为List编写代码要比我写得好得多：我不想实现其他人已经实现的东西d