面试中最常见的问题之一。。。在N个数中间寻找前K大个元素
最常见的解法就是最大堆 时间复杂度O(N*log(K)) 空间复杂度O(k)
实现了一个最简单的最大堆，每次有元素进来都和堆顶元素比较一下，如果新元素比较大就替换，然后就逐级更新到堆底
namespace Clover.Algoritms.DataStructure
{
using System;
using System.ComponentModel;
using System.Linq.Expressions;
using System.Reflection;
using System.Runtime.CompilerServices;
using System.Threading; using Clover.Algoritms.Common; public class MaxHeap
{
public double[] items; public int count = ; public MaxHeap(int capacity)
{
if (capacity <= )
{
throw new ArgumentOutOfRangeException("capacity");
}
this.items = new double[capacity];
for (int i = ; i < this.items.Length; i++)
{
this.items[i] = double.MinValue;
}
} public bool Validate()
{
for (int i = ; i < this.items.Length; i++)
{
int left = * i + ;
int right = * i + ;
if (left < this.items.Length)
{
if (this.items[left] > this.items[i])
{
return false;
}
}
if (right < this.items.Length)
{
if (this.items[right] > this.items[i])
{
return false;
}
}
}
return true;
} public void MaxHeapify(int i, int size = -)
{
var s = size > ? size : items.Length;
if (i >= s)
{
return;
} var l = this.left(i);
var r = this.right(i);
var largest = i;
if (l < s && items[l] > items[i])
{
largest = l;
}
if (r < s && items[r] > items[largest])
{
largest = r;
}
if (largest != i)
{
var temp = items[i];
items[i] = items[largest];
items[largest] = temp;
MaxHeapify(largest);
}
} public void BuildMaxHeap()
{
for (int i = items.Length / ; i >= ; i--)
{
this.MaxHeapify(i);
}
} public int left(int i)
{
return i * + ;
} public int right(int i)
{
return i * + ;
} public int parent(int i)
{
return i / - ;
} public void HeapSort()
{
this.BuildMaxHeap();
for (int i = items.Length / ; i >= ; i--)
{
var temp = items[];
items[] = items[i];
items[i] = temp;
var size = items.Length - - items.Length / + i;
this.MaxHeapify(i, size);
}
} //max heap is used to find top k smallest items.
public void PickTopN(double d)
{
if (count < items.Length)
{
items[count] = d;
count++;
if (count >= items.Length)
{
this.BuildMaxHeap();
}
}
else if (d < items[])
{
items[] = d;
this.MaxHeapify();
}
} public double Maximun()
{
if (count == )
{
throw new Exception("there is no any element in heap");
} return items[];
} public double HeapExtractMax()
{
if (count == )
{
throw new Exception("there is no any element in heap");
}
var max = items[];
items[] = items[count];
count--;
this.MaxHeapify();
return max;
} public void MaxHeapInsnsert(double d)
{
count++;
double[] newItems = new double[count];
for (int i = ; i < count - ; i++)
{
newItems[i] = items[i];
}
newItems[count - ] = double.MinValue;
items = newItems;
MaxHeapIncreaseKey(count - , d);
} private void MaxHeapIncreaseKey(int ind, double d)
{
var i = ind;
if (d < items[i])
{
throw new Exception("new key is smaller than than current key");
}
items[i] = d;
while (i > && items[this.parent(i)] < items[i])
{
ObjectExtension.Exhange(ref items[i], ref items[this.parent(i)]);
i = this.parent(i);
}
}
}
}