引入
這2天都好囧，很久沒有寫了。今天說說堆與映射。
平常，我們用堆，最常見的就是隨機(jī)地加入元素，隨機(jī)地取最大值或最小值。這些基本的操作C++中的priority_queue和set都能很好的完成，而且C++中還有一個(gè)make_heap，效率較前面2個(gè)會(huì)更高。而且前面提到的STL都是采用紅黑樹實(shí)現(xiàn)的，很具有穩(wěn)定性。
上面的堆雖然使用簡單，但功能上還是有些局限。比如前面提到的堆都只能實(shí)現(xiàn)刪除最值并沒有辦法刪除指定的值。而且一般STL中的堆都是采用數(shù)據(jù)存儲(chǔ)的，但父親節(jié)點(diǎn)和兒子節(jié)點(diǎn)需要交換時(shí)，我們需要拷貝所存儲(chǔ)的整個(gè)數(shù)據(jù)單元，但數(shù)據(jù)單元較大時(shí)，拷貝的效率就低了。因此，這里介紹一中堆變種，在堆中引入了映射。
定義
具有映射功能的堆稱為雙向映射堆。又其常常是在二分堆的基礎(chǔ)上實(shí)現(xiàn)的，所以也常常叫映射二分堆。
特點(diǎn)
映射二分堆其與普通堆不同的地方是它的節(jié)點(diǎn)并不真正保存數(shù)據(jù)單元本身，而是保存指向數(shù)據(jù)單元的指針。因此當(dāng)需要交換父子節(jié)點(diǎn)的數(shù)據(jù)時(shí)，我們可以避免拷貝大量數(shù)據(jù)所消耗的時(shí)間。同時(shí)，映射二分堆還有一個(gè)功能可以根據(jù)具體的數(shù)據(jù)單元的索引來刪除該單元，即使這個(gè)單元不是堆中的最值。
實(shí)現(xiàn)方法
在實(shí)現(xiàn)是，我們可以用數(shù)字H[]存儲(chǔ)數(shù)據(jù)單元，然后采用數(shù)組ind[i]=j表示H[i]存放的是索引號(hào)為j的數(shù)據(jù)，mp[i]=j表示索引索引為i的元素存儲(chǔ)在H[j]中，這樣就可以實(shí)現(xiàn)雙向映射了。
插入堆，我們只需要將插入的元素放在堆尾，然后逐級(jí)調(diào)整，這個(gè)跟普通的二叉堆一樣樣。
刪除最值，也跟普通的二叉堆一樣，先把堆中最后一個(gè)元素與最值對調(diào)，然后在調(diào)整堆。
增加一個(gè)的是刪除固定索引的數(shù)據(jù)單元，我們可以先通過mp[i]，找到其在H[]中存放的位置，然后該位置的值跟堆最后一個(gè)元素對調(diào)，接著從該節(jié)點(diǎn)向上調(diào)整堆，此時(shí)得到的還不是一個(gè)正規(guī)的堆，還需要重新堆整個(gè)堆進(jìn)行從上到下調(diào)整。
上面的3中操作中都提到了堆的調(diào)整，還是上面說的，調(diào)整時(shí)我們不需要拷貝數(shù)據(jù)單元，我們只需交換ind[]和mp[]2個(gè)數(shù)組的對應(yīng)值即可。
應(yīng)用
acm題目中，典型可以使用映射堆解決的題目是FOJ 1209 最小權(quán)無前綴語言問題,這道題在LRJ的書講得很詳細(xì)，但他把這題目命名為最輕巧的語言，在P91。具體的方法我就不多說了，因?yàn)長RJ那里已經(jīng)很具體了。
最后貼一個(gè)一個(gè)未成型的映射堆的代碼，之所以說為成型，是因?yàn)檫@個(gè)堆寫得不是很清晰，未把映射堆用類封裝起來，代碼讀起來比較辛苦。代碼來源dou。代碼對應(yīng)題目是poj
2442 Sequence
#include<stdio.h>
#include<string>
#include<algorithm>
usingnamespace
std;
#define
N 2010
#define
inf 0x7fffffff
intdata1[N],
data2[N], data3[N];
intpoint[N];
intheap[N];
structnode
{
intnum;
inttoheap;
}
que[N];
intn;
voidmovedown()
{
inti
= 1;
intl,
r;
while(1)
{
l
= 2 * i;
r
= l + 1;
if(l
> n)
break;
if(que[heap[i]].num
> que[heap[l]].num && ((r <= n && que[heap[l]].num <= que[heap[r]].num) || r > n)) {
swap(que[i].toheap,
que[l].toheap);
swap(heap[i],
heap[l]);
i
= l;
}else
if(que[heap[i]].num
> que[heap[r]].num && r <= n && que[heap[r]].num <= que[heap[l]].num) {
swap(que[i].toheap,
que[r].toheap);
swap(heap[i],
heap[r]);
i
= r;
}elsebreak;
}
}
intmain()
{
intcas;
inttemp;
scanf("%d",
&cas);
while(cas--)
{
inti,
j;
intm;
scanf("%d%d",
&m, &n);
for(i
= 1; i <= n; ++i)
scanf("%d",
data1 + i);
sort(data1
+ 1, data1 + n + 1);
for(j
= 0; j < m - 1; ++j) {
for(i
= 1; i <= n; ++i)
scanf("%d",
data2 + i);
sort(data2
+ 1, data2 + n + 1);
data2[n
+ 1] = inf;
for(i
= 1; i <= n; ++i) {
que[i].num
= data1[i] + data2[1];
que[i].toheap
= i;
heap[i]
= i;
point[i]
= 1;
}
for(i
= 1; i <= n; ++i) {
data3[i]
= que[heap[1]].num;
point[heap[1]]++;
temp
= data1[heap[1]] + data2[point[heap[1]]];
que[heap[1]].num
= temp;
movedown();
}
memcpy(data1,
data3, 4 * (n + 1));
}
printf("%d",
data1[1]);
for(i
= 2; i <= n; ++i)
printf("
%d",
data1[i]);
printf("n");
}
return0;
}
|
|
