在上一篇博客中,记录了优先队列——堆这个数据结构的实现,并且关于堆的性质我也在上文中介绍过,堆能用来进行排序,堆排序具有快速(复杂度O(NlogN)),稳定的特点,尤其是非常稳定,因此适用于某些需要排序稳定性的场合。
但是呢,普通的二叉堆有两个缺陷:
第一个缺陷还能用类似于指针排序的技术解决,但是第二个缺陷不采用特殊的技术是没有办法解决的,然而在一些场合,堆中元素的值确实需要改变。于是乎,索引堆这个数据结构就在这里应运而生了。
所谓索引堆,简单的说,就是在堆里头存放的不是数据,而是数据所在的数组的索引,也就是下标,根据数据的某种优先级来调整各个元素对应的下标在堆中的位置。本质上来说,索引堆也是堆,提供堆的接口。
那么接下来,我们就来尝试用C++
和J�ava
两种语言来实现索引堆,注释在代码中写的比较详细。
C++版如下:
#include <iostream> using namespace std; template<typename Item> class IndexMaxHeap { private: Item *data; int *indexes; int *reverse; int count; int capacity; void shiftUp( int k ) { while (k > 1 && data[ indexes[k/2] ] < data[ indexes[k] ]) { swap( indexes[k/2], indexes[k] ); reverse[indexes[k / 2]] = k / 2; reverse[indexes[k]] = k; k /= 2; } } void shiftDown( int k ) { while (2*k <= count) { int j = 2 * k; // 在此轮循环中,data[k]和data[j]交换位置 if (j + 1 <= count && data[ indexes[j] ] < data[ indexes[j+1] ]) // data[j] 是 data[2*k]和data[2*k+1]中的最大值 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: // 构造函数, 构造一个空的索引堆, 可容纳capacity个元素 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; } count = 0; this->capacity = capacity; } IndexMaxHeap(Item arr[], int n) { data = new Item[n+1]; capacity = n + 1; for (int i = 0; i < n; i++) data[i+1] = arr[i]; count = n; for (int i = count / 2; i >= 1; i--) shiftDown(i); } ~IndexMaxHeap() { delete[] data; delete[] indexes; delete[] reverse; } // 返回堆中的元素个数 int size() { return count; } // 返回一个布尔值, 表示堆中是否为空 bool isEmpty() { return count == 0; } // 向最大索引堆中插入一个新的元素, 新元素的索引为i, 元素为item // 传入的i对用户而言,是从0索引的 void insert(int i, Item item) { assert(count + 1 <= capacity); assert(i + 1 >= 1 && i + 1 <= capacity); // 再插入一个新元素前,还需要保证索引i所在的位置是没有元素的。 assert( !contain(i) ); i += 1; data[i] = item; indexes[count+1] = i; reverse[i] = count + 1; count++; shiftUp( count ); } // 从最大堆中取出堆顶元素, 即堆中所存储的最大数据 Item extractMax() { assert(count > 0); Item ret = data[ indexes[1] ]; swap( 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; swap( indexes[1], indexes[count] ); reverse[ indexes[1] ] = 1; reverse[ indexes[count] ] = 0; count--; shiftDown(1); return ret; } 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]在堆中的位置 // 之后shiftUp(j), 再shiftDown(j) // for ( int j = 1; j <= count; j++ ) { // if (indexes[j] == i) { // shiftUp(j); // shiftDown(j); // return; // } // } // 有了 reverse 之后, // 我们可以非常简单的通过reverse直接定位索引i在indexes中的位置 int j = reverse[i]; shiftUp(j); shiftDown(j); } // 获取最大堆中的堆顶元素 Item getMax(){ assert( count > 0 ); return data[1]; } // 测试索引堆中的索引数组index和反向数组reverse // 注意:这个测试在向堆中插入元素以后, 不进行extract操作有效 bool testIndexesAndReverseIndexes(){ int *copyIndexes = new int[count+1]; int *copyReverseIndexes = new int[count+1]; for( int i = 0 ; i <= count ; i ++ ){ copyIndexes[i] = indexes[i]; copyReverseIndexes[i] = reverse[i]; } copyIndexes[0] = copyReverseIndexes[0] = 0; std::sort(copyIndexes, copyIndexes + count + 1); std::sort(copyReverseIndexes, copyReverseIndexes + count + 1); // 在对索引堆中的索引和反向索引进行排序后, // 两个数组都应该正好是1...count这count个索引 bool res = true; for( int i = 1 ; i <= count ; i ++ ) if( copyIndexes[i-1] + 1 != copyIndexes[i] || copyReverseIndexes[i-1] + 1 != copyReverseIndexes[i] ){ res = false; break; } delete[] copyIndexes; delete[] copyReverseIndexes; if( !res ){ cout<<"Error!"<<endl; return false; } for( int i = 1 ; i <= count ; i ++ ) if( reverse[ indexes[i] ] != i ){ cout<<"Error 2"<<endl; return false; } return true; } };
Java版本的代码如下:
// 最大索引堆 public class IndexMaxHeap<Item extends Comparable> { protected Item[] data; // 最大索引堆中的数据 protected int[] indexes; // 最大索引堆中的索引, indexes[x] = i 表示索引i在x的位置 protected int[] reverse; // 最大索引堆中的反向索引, reverse[i] = x 表示索引i在x的位置 protected int count; protected int capacity; // 构造函数, 构造一个空堆, 可容纳capacity个元素 public IndexMaxHeap(int capacity) { data = (Item[]) new Comparable[capacity + 1]; indexes = new int[capacity + 1]; reverse = new int[capacity + 1]; for (int i = 0; i <= capacity; i++) { reverse[i] = 0; } count = 0; this.capacity = capacity; } // 返回索引堆中的元素个数 public int size() { return count; } // 返回一个布尔值, 表示索引堆中是否为空 public boolean isEmpty() { return count == 0; } // 向最大索引堆中插入一个新的元素, 新元素的索引为i, 元素为item // 传入的i对用户而言,是从0索引的 public void insert(int i, Item item) { assert (count + 1 <= capacity); assert (i + 1 >= 1 && i + 1 <= capacity); // 再插入一个新元素前,还需要保证索引i所在的位置是没有元素的。 assert ( !contain(i) ); i += 1; data[i] = item; indexes[count + 1] = i; reverse[i] = count + 1; count++; shiftUp( count ); } // 从最大索引堆中取出堆顶元素, 即索引堆中所存储的最大数据 public Item extractMax() { assert (count > 0); Item ret = data[ indexes[1] ]; swap(indexes, 1, count); reverse[ indexes[1] ] = 1; reverse[ indexes[count] ] = 0; count--; shiftDown(1); return ret; } // 从最大索引堆中取出堆顶元素的索引 int extractMaxIndex() { assert (count > 0); int ret = indexes[1] - 1; swap(indexes, 1, count); reverse[ indexes[1] ] = 1; reverse[ indexes[count] ] = 0; count--; shiftDown(1); return ret; } // 看索引i所在的位置是否存在元素 private boolean contain(int i) { assert (i + 1 >= 1 && i + 1 <= capacity); return reverse[i+1] != 0; } private void shiftUp(int k) { while (k > 1 && data[ indexes[k / 2] ].compareTo( data[ indexes[k] ] ) < 0) { swap(indexes, k / 2, k); k /= 2; } } private void shiftDown(int k) { while (2*k <= count) { int j = 2 * k; if (j + 1 <= count && data[ indexes[j] ].compareTo( data[ indexes[j+1] ] ) < 0) { j += 1; } if (data[ indexes[k] ].compareTo(data[ indexes[j] ]) > 0) { break; } swap(indexes, k, j); k = j; } } // 交换索引堆中的索引i和j // 由于有了反向索引reverse数组, // indexes数组发生改变以后, 相应的就需要维护reverse数组 private void swap(int[] arr, int i, int j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; reverse[ indexes[i] ] = i; reverse[ indexes[j] ] = j; } // 获取最大索引堆中索引为i的元素 public Item getItem(int i) { assert (contain(i)); return data[i + 1]; } // 将最大索引堆中索引为i的元素修改为newItem public void change(int i, Item newItem) { assert(contain(i)); i += 1; data[i] = newItem; int j = reverse[i]; shiftUp(j); shiftDown(j); } // 获取最大索引堆中的堆顶元素 Item getMax() { assert (count > 0); return data[1]; } // 测试索引堆中的索引数组index和反向数组reverse // 注意:这个测试在向堆中插入元素以后, 不进行extract操作有效 public boolean testIndexes(){ int[] copyIndexes = new int[count+1]; int[] copyReverseIndexes = new int[count+1]; for( int i = 0 ; i <= count ; i ++ ) { copyIndexes[i] = indexes[i]; copyReverseIndexes[i] = reverse[i]; } copyIndexes[0] = 0; copyReverseIndexes[0] = 0; Arrays.sort(copyIndexes); Arrays.sort(copyReverseIndexes); // 在对索引堆中的索引和反向索引进行排序后, // 两个数组都应该正好是1...count这count个索引 boolean res = true; for( int i = 1 ; i <= count ; i ++ ) if( copyIndexes[i-1] + 1 != copyIndexes[i] || copyReverseIndexes[i-1] + 1 != copyReverseIndexes[i] ){ res = false; break; } if( !res ){ System.out.println("Error!"); return false; } return true; } public static void main(String[] args) { int N = 1000000; IndexMaxHeap<Integer> indexMaxHeap = new IndexMaxHeap<Integer>(N); for (int i = 0; i < N; i++) { indexMaxHeap.insert(i, (int) (Math.random() * N)); } assert indexMaxHeap.testIndexes(); } }
本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。
我来说两句