1. 前言

本文为笔者原创~~的乱搞文章~~，如有雷同，纯属偶然。转载请注明出处。

2. 引入

有时候我们要求一些数里前

k

大的数，其中

k

为一个较小的常数，不值得使用

\Theta(n \log n)

的排序算法。于是想到线性查找。

k=2

时：

CPP

for(int i=1;i<=n;i++)
{
	if(a[i]>Max1)
	{
		Max2=Max1;
		Max1=a[i];
	}
	else if(a[i]>Max2)
		Max2=a[i];
}

k=4

时：

CPP

for(int i=1;i<=n;i++)
{
	if(a[i]>Max1)
	{
		Max4=Max3;
		Max3=Max2;
		Max2=Max1;
		Max1=a[i];
	}
	else if(a[i]>Max2)
	{
		Max4=Max3;
		Max3=Max2;
		Max2=a[i];
	}
	else if(a[i]>Max3)
	{
		Max4=Max3;
		Max3=a[i];
	}
	else if(a[i]>Max4)
		Max4=a[i];
}

可以想象当

k=8

时代码会有多少冗长。

3. Priority Array

于是想到可以用一种暴力乱搞的数据结构去取代这些多余的代码，支持快速插入一个数，查询第

k

大的数。

不难想到暴力维护一个大小为

\Theta(k)

数组，每次从末端插入一个数然后暴力冒泡到前面。我称他为优先数组（Priority Array）。

这个数据结构可以

\Theta(k)

插入一个数，

\Theta(1)

查询第

k

大的数，空间复杂度

\Theta(k)

，其中

k

为一个较小的常数。时间当

\Theta(k)<\Theta(\log n)

时要优于排序或者堆，空间上优于堆，支持在线查询。

4. 实现

CPP

template<typename T,size_t s>
struct priority_array
{
	T a[s+2];
	size_t n;
	priority_array(void)
	{
		n=0;
		memset(a,0,sizeof(a));
	}
	size_t size(void)
	{
		return n;
	}
	bool empty(void)
	{
		return n==0;
	}
	void insert(T x)
	{
		if(n<=s)n++;
		a[n]=x;
		size_t y=n;
		while(y&&a[y-1]<a[y])
		{
			swap(a[y],a[y-1]);
			y--;
		}
	}
	T top(const int&x)const&
	{
		assert(x<=s);
		return a[x];
	}
};

定义一个 int 型，大小为

5

的优先数组：

CPP

priority_array<int,5>pa;

也可以定义其他类型的，例如：

CPP

priority_array<long long,5>pa;
priority_array<string,10>pa;
priority_array<pair<int,int>,2>pa;
struct S
{
  int x,y,z;
  bool operator<(const S&i)const&
  {
    return x<i.x||x==i.x&&y<i.y;
  }//记得重载小于运算符
}
priority_array<S,10>pa;

这些都是可以的。

插入一个数

x

：pa.insert(x);

返回第

k

大的数：pa.top(k);
其中

k

是 0-index 的。

返回优先数组的大小：pa.size();

返回是否为空：pa.empty();

总结

优先数组这种数据结构能够快速简洁地求出一些数里面第

k

大的数~~虽然没用~~。

A New Data Structure: Priority Array

文章操作