A New Data Structure: Priority Array
BitByBit
·
·
算法·理论
1. 前言
本文为笔者原创的乱搞文章，如有雷同，纯属偶然。转载请注明出处。
2. 引入
有时候我们要求一些数里前 k 大的数，其中 k 为一个较小的常数，不值得使用 \Theta(n \log n) 的排序算法。于是想到线性查找。
```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;
```
也可以定义其他类型的，例如：
```
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$ 大的数~~虽然没用~~。