索引堆
之前建立堆的過程中所存在的問題
將一個數(shù)組進行 heapify 之后, 數(shù)組元素的位置發(fā)生了變化, 有兩個缺點:
- 移動元素位置可能會造成大量的性能消耗.
- 在有些情況下, 元素位置有其他意義, 不能隨意改變元素位置.
建立索引堆
image
針對每一個元素, 添加一個 index 結(jié)構(gòu), 用來完成堆的建立. 建立完成后, 原數(shù)組元素位置不變, index 的值表示在堆中對應(yīng)位置的元素位置. 例如: 位置為 1 的 index 值為 10, arr[10] 位于堆的根節(jié)點, 其左孩子 index 值為 9, 表示 arr[9] 為根節(jié)點的左孩子.
在元素比較時, 比較的是 data 數(shù)據(jù), 在做元素交換時交換的是 index.
索引數(shù)組的含義, 是從堆的角度, 正向的理解, 即 indexes[i] 表示, 堆中第 i 個元素對應(yīng)的數(shù)據(jù)為 data[indexes[i]] (其索引為 indexes[i]).
代碼實現(xiàn)
相比較于之前最大堆的實現(xiàn), 改造為索引堆是很容易的, 需要做的是以下幾件事:
- 添加索引數(shù)組, 其大小與數(shù)據(jù)大小相同.
- 在用戶插入元素時, 需要給定該元素的索引, 該元素在數(shù)組的位置.
- 在比較元素大小時, 我們獲取到的索引為堆中的索引
k, 需要通過indexes[k]的方式轉(zhuǎn)換為數(shù)據(jù)的索引. - 在交換元素時, 只需要交換其在
indexes數(shù)組中的位置swap(indexes[k], indexes[k / 2]).
完整的索引堆實現(xiàn)如下:
template<typename Item>
class IndexMaxHeap {
private:
Item *data;
int *indexes;
int count;
int capacity{};
// 將 k 這個元素向上移動, 以滿足大根堆定義
void shiftUp(int k) {
while (k > 1 && data[indexes[k / 2]] < data[indexes[k]]) {
swap(indexes[k], indexes[k / 2]);
k /= 2;
}
}
void shiftDown(int k) {
while (2 * k <= count) {
int j = 2 * k;
if (j + 1 <= count && data[indexes[j + 1]] > data[indexes[j]]) {
j += 1;
}
if (data[indexes[k]] >= data[indexes[j]]) {
break;
}
swap(indexes[k], indexes[j]);
k = j;
}
}
public:
IndexMaxHeap(int capacity) {
data = new Item[capacity + 1];
indexes = new int[capacity + 1];
this->capacity = capacity;
count = 0;
}
IndexMaxHeap(Item arr[], int n) {
data = new Item[n + 1];
indexes = new int[capacity + 1];
this->capacity = n;
count = n;
for (int i = 0; i < n; i++) {
data[i + 1] = arr[i];
}
for (int i = count / 2; i >= 1; i--) {
shiftDown(i);
}
}
~IndexMaxHeap() {
delete[] data;
delete[] indexes;
}
int size() {
return count;
}
bool isEmpty() {
return count == 0;
}
// 傳入的 i 對于用戶來說, 是從 0 開始索引的
void insert(int i, Item item) {
assert(count + 1 <= capacity);
assert(i + 1 >= 1 && i + 1 <= capacity);
i += 1;
data[++count] = item;
indexes[++count] = i;
shiftUp(count);
}
Item extractMax() {
assert(count > 0);
Item ret = data[indexes[1]];
indexes[1] = indexes[count--];
shiftDown(1);
return ret;
}
// 返回最大元素的的索引
int extractMaxIndex() {
assert(count > 0);
// 對于外部用戶來說, 索引減一
int ret = indexes[1] - 1;
indexes[1] = indexes[count--];
shiftDown(1);
return ret;
}
Item getItem(int i) {
return data[i + 1];
}
void change(int i, Item newItem) {
i += 1;
data[i] = newItem;
// 找到 indexes[j] = i, j 表示 data[i] 在堆中的位置.
for (int j = 1; j <= count; j++) {
if (indexes[j] == i) {
shiftUp(j);
shiftDown(j);
return;
}
}
}
};
change 操作
在上面的實現(xiàn)中, 添加了一個新的操作 create(), 用于修改指定數(shù)據(jù)位置的數(shù)據(jù)內(nèi)容. 在實現(xiàn)中, 我們需要找到該數(shù)據(jù)對應(yīng)于堆中的位置, 即找到一個 j, 使得 indexes[j] = i.
void change(int i, Item newItem) {
i += 1;
data[i] = newItem;
// 找到 indexes[j] = i, j 表示 data[i] 在堆中的位置.
for (int j = 1; j <= count; j++) {
if (indexes[j] == i) {
shiftUp(j);
shiftDown(j);
return;
}
}
}
在上面的實現(xiàn)中, 我們通過遍歷整個 indexes 數(shù)組, 找到和 i 相匹配的元素. 這一步操作的時間復(fù)雜度是 , 因為后續(xù)
shiftUp() 和 shiftDown() 操作復(fù)雜度都為 , 因此總體的時間復(fù)雜度可以看做
. 如果同時對 n 個堆進行操作, 時間復(fù)雜度就達到了
.
進一步改進
為了降低時間復(fù)雜度, 這里一個通用的方法就是建立反向索引數(shù)組, 如下圖所示:
image
數(shù)組 rev 表示反向索引, 其含義為, 站在數(shù)據(jù)的角度來看, 這個數(shù)據(jù)所對應(yīng)于堆中的位置是多少. 例如, 位于 10 處的數(shù)據(jù), 對應(yīng)于堆中的位置為 1, 即其位于根節(jié)點.
-
reverse[i]表示索引i在indexes(堆) 中的位置
根據(jù)其定義, 有下面兩個等式成立
indexes[reverse[i]] = ireverse[indexes[i]] = i
在進行位置變更時, 需要同時變更:
indexes[i] = jreverse[j] = i
完整的實現(xiàn)如下:
template<typename Item>
class IndexMaxHeap {
private:
Item *data;
int *indexes;
int *reverse;
int count;
int capacity{};
// 將 k 這個元素向上移動, 以滿足大根堆定義
void shiftUp(int k) {
while (k > 1 && data[indexes[k / 2]] < data[indexes[k]]) {
swap(indexes[k], indexes[k / 2]);
reverse[indexes[k / 2]] = k / 2;
reverse[indexes[k]] = k;
k /= 2;
}
}
void shiftDown(int k) {
while (2 * k <= count) {
int j = 2 * k;
if (j + 1 <= count && data[indexes[j + 1]] > data[indexes[j]]) {
j += 1;
}
if (data[indexes[k]] >= data[indexes[j]]) {
break;
}
swap(indexes[k], indexes[j]);
reverse[indexes[k]] = k;
reverse[indexes[j]] = j;
k = j;
}
}
public:
IndexMaxHeap(int capacity) {
data = new Item[capacity + 1];
indexes = new int[capacity + 1];
reverse = new int[capacity + 1];
for (int i = 0; i <= capacity; i++) {
// reverse[i] = 0 表示數(shù)據(jù) i 在堆中不存在.
reverse[i] = 0;
}
this->capacity = capacity;
count = 0;
}
IndexMaxHeap(Item arr[], int n) {
data = new Item[n + 1];
indexes = new int[capacity + 1];
reverse = new int[capacity + 1];
reverse = new int[capacity + 1];
for (int i = 0; i <= capacity; i++) {
// reverse[i] = 0 表示數(shù)據(jù) i 在堆中不存在.
reverse[i] = 0;
}
this->capacity = n;
count = n;
for (int i = 0; i < n; i++) {
data[i + 1] = arr[i];
}
for (int i = count / 2; i >= 1; i--) {
shiftDown(i);
}
}
~IndexMaxHeap() {
delete[] data;
delete[] indexes;
}
int size() {
return count;
}
bool isEmpty() {
return count == 0;
}
// 傳入的 i 對于用戶來說, 是從 0 開始索引的
void insert(int i, Item item) {
assert(count + 1 <= capacity);
assert(i + 1 >= 1 && i + 1 <= capacity);
i += 1;
data[++count] = item;
indexes[++count] = i;
reverse[i] = count;
shiftUp(count);
}
Item extractMax() {
assert(count > 0);
Item ret = data[indexes[1]];
indexes[1] = indexes[count];
reverse[indexes[1]] = 1;
reverse[indexes[count]] = 0;
count--;
shiftDown(1);
return ret;
}
// 返回最大元素的的索引
int extractMaxIndex() {
assert(count > 0);
// 對于外部用戶來說, 索引減一
int ret = indexes[1] - 1;
indexes[1] = indexes[count];
reverse[indexes[1]] = 1;
reverse[indexes[count]] = 0;
shiftDown(1);
return ret;
}
// 判斷數(shù)組下標為 i 的元素, 是否存在于堆中
bool contain(int i) {
assert(i + 1 >= 1 && i + 1 <= capacity);
return reverse[i + 1] != 0;
}
Item getItem(int i) {
assert(contain(i));
return data[i + 1];
}
void change(int i, Item newItem) {
assert(contain(i));
i += 1;
data[i] = newItem;
// 找到 indexes[j] = i, j 表示 data[i] 在堆中的位置.
int j = reverse[i];
shiftUp(j);
shiftDown(j);
return;
}
};
