索引最大堆

索引最大堆

索引堆的核心思想，根据data数组改变index 数组，比较的是data的数据，而交换的数据是index数据

堆是具有以下特性的完全二叉树，每个结点的值都大于或等于其左右孩子结点的值，叫最大堆，每个结点的值都小于或等于其左右孩子结点的值，叫做最小堆。

初始数据：

对应的索引堆

#pragma once//---------------------------------------索引最大堆的搭建----------------------------------------------//索引堆的核心思想，根据data数组改变index 数组，比较的是data的数据，而交换的数据是index数据//本堆的索引是从1开始的，但对于用户来说，是从0开始的，故会接口索引进行处理template class IndexMaxHeap{private: Item* data; int* indexes; //堆中已经存放了多少堆元素 int count; //可以存放多少个堆元素 int capacity; //私有属性，对象调用不了，用户调用Insert函数就可以了 //k,为索引值 void shiftUp(int k) { while (k > 1 && data[indexes[k]] > data[indexes[k / 2]]) { swap(indexes[k], indexes[k / 2]); k /= 2; } } //如果有左右孩子，则找出左右孩子的最大值索引，跟父节点比较，如果父节点比他们大，则跳出，反之则交换 //k,为索引值 void shiftDown(int k) { while (2 * k <= count) { //j存放孩子的最大值索引，默认为左孩子 int j = 2 * k; //要考虑j边界问题 if (j + 1 <= count && data[indexes[j + 1]] > data[indexes[j]]) { j += 1; } //此时j是最大的索引 if (data[indexes[k]] >= data[indexes[j]]) break; swap(indexes[k], indexes[j]); k = j; } }public: //一个一个的插入元素 IndexMaxHeap(int capacity) { //因为堆的根节点索引从1开始 data = new Item[capacity + 1]; indexes = new int[capacity + 1]; count = 0; this->capacity = capacity; } //heapify的过程，算法复杂度为O(n)，将n个元素逐个插到一个空堆中，算法复杂度是O(nlogn) //n,为数组的个数 IndexMaxHeap(Item arr[], int n) { data = new Item[n + 1]; indexes = new int[n + 1]; for (int i = 0; i < n; i++) { data[i + 1] = arr[i]; indexes[i+1] = i+1; } count = n; capacity = n; 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) { //capacity 代表着类的容量，所以每次传入的索引，或者怎加元素，都得先判断是否超出容量 assert(count + 1 <= capacity); assert(i >= 0 && i + 1 <= capacity); //我们的堆是从1开始索引的，所以得将用户输入的i加1 i = i + 1; data[i] = item; indexes[count + 1] = i; //覆盖不属于堆中的元素，即将不是堆的元素变成了堆的元素，故堆的元素数量要+1 count++; shiftUp(count); } //从堆中提取元素，数组中堆以外的元素不是为空，而是有值得数，是从根节点替换下来的 Item extractMax() { assert(count >= 1); Item pop = data[indexes[1]]; swap(indexes[1], indexes[count]); count--; shiftDown(1); return pop; } //返回当前堆中最大值的索引 int extractMaxIndex() { assert(count >= 1); //用户以为是从0索引的 Item pop = indexes[1]-1; swap(indexes[1], indexes[count]); count--; shiftDown(1); return pop; } //用户已知某个元素的索引，返回这个索引对应的值，用户以为是从0索引的，故i+1 Item getItem(int i) { return data[i + 1]; } //用户更换索引i对应的值，用户以为是从0索引的，故i+1 void change(int i, Item newItem) { i = i + 1; data[i] = newItem; //找到indexes[j]=i;j表示data[i]在堆中位置 //之后shiftup(j),再shifedown(j) for (int j = 1; j <= count; j++) { if (indexes[j] == i) { shiftUp(j); shiftDown(j); return; } } }};//测试代码void indexmaxheap(int arr[], int n){ IndexMaxHeapindexmaxheap = IndexMaxHeap(arr, n); while (!indexmaxheap.isEmpty()) { cout << indexmaxheap.extractMax() << endl; }}//测试代码//-------------------索引堆的调试程序-------------------- IndexMaxHeapindexmaxheap = IndexMaxHeap(50); cout << "indexmaxheap size:" << indexmaxheap.size() << endl; srand(time(NULL)); for (int heap_i = 0; heap_i < 50; heap_i++) { indexmaxheap.Insert(heap_i, rand() % 50); } indexmaxheap.change(10, 100); cout << indexmaxheap.getItem(10) << " "; while (!indexmaxheap.isEmpty()) { cout << indexmaxheap.extractMax() << endl; }

上述代码思路，如果用户更换索引i对应的值，我们需要遍历一次indexes数组，才能找到indexes[j]=i的值，无疑增加了时间复杂度。下述思路很好的解决了这个问题。 让我们轻松地知道了，索引i在什么index的什么位置处。

#pragma once//---------------------------------------索引最大堆的搭建----------------------------------------------//索引堆的核心思想，根据data数组改变index 数组，比较的是data的数据，而交换的数据是index数据//本堆的索引是从1开始的，但对于用户来说，是从0开始的，故会接口索引进行处理template class IndexMaxHeap{private: Item* data; int* indexes; //代表着data[i]的索引i，在index数组中的什么位置 reverse[i]返回的是data[i]中的i的索引位置 int* reverse; //堆中已经存放了多少堆元素 int count; //可以存放多少个堆元素 int capacity; //私有属性，对象调用不了，用户调用Insert函数就可以了 //k,为索引值 void shiftUp(int k) { while (k > 1 && data[indexes[k]] > data[indexes[k / 2]]) { swap(indexes[k], indexes[k / 2]); reverse[indexes[k/2]] = k / 2; reverse[indexes[k]] = k; k /= 2; } } //如果有左右孩子，则找出左右孩子的最大值索引，跟父节点比较，如果父节点比他们大，则跳出，反之则交换 //k,为索引值 void shiftDown(int k) { while (2 * k <= count) { //j存放孩子的最大值索引，默认为左孩子 int j = 2 * k; //要考虑j边界问题 if (j + 1 <= count && data[indexes[j + 1]] > data[indexes[j]]) { j += 1; } //此时j是最大的索引 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) { //因为堆的根节点索引从1开始 data = new Item[capacity + 1]; indexes = new int[capacity + 1]; reverse = new int[capacity + 1]; //堆中没有元素的时候，reverse 数组必须先默认全为0 for (int i = 0; i <= capacity; i++) reverse[i] = 0; count = 0; this->capacity = capacity; } //heapify的过程，算法复杂度为O(n)，将n个元素逐个插到一个空堆中，算法复杂度是O(nlogn) //n,为数组的个数 IndexMaxHeap(Item arr[], int n) { data = new Item[n + 1]; indexes = new int[n + 1]; reverse = new int[n + 1]; //堆中没有元素的时候，reverse 数组必须先默认全为0 for (int i = 0; i <= capacity; i++) reverse[i] = 0; for (int i = 0; i < n; i++) { data[i + 1] = arr[i]; indexes[i+1] = i+1; } count = n; capacity = 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对用户而言，是从0索引的 void Insert(int i,Item item) { //capacity 代表着类的容量，所以每次传入的索引，或者怎加元素，都得先判断是否超出容量 assert(count + 1 <= capacity); assert(i >= 0 && i + 1 <= capacity); //我们的堆是从1开始索引的，所以得将用户输入的i加1 i = i + 1; data[i] = item; indexes[count + 1] = i; reverse[i] = count + 1; //覆盖不属于堆中的元素，即将不是堆的元素变成了堆的元素，故堆的元素数量要+1 count++; shiftUp(count); } //从堆中提取元素，数组中堆以外的元素不是为空，而是有值得数，是从根节点替换下来的 Item extractMax() { assert(count >= 1); Item pop = data[indexes[1]]; swap(indexes[1], indexes[count]); reverse[indexes[1]] = 1; //此时indexes[count]中的data的索引对应的元素并非堆中元素了 reverse[indexes[count]] =0; count--; shiftDown(1); return pop; } //返回当前堆中最大值的索引 int extractMaxIndex() { assert(count >= 1); //用户以为是从0索引的 Item pop = indexes[1]-1; swap(indexes[1], indexes[count]); reverse[indexes[1]] = 1; //此时indexes[count]中的data的索引对应的元素并非堆中元素了 reverse[indexes[count]] = 0; count--; shiftDown(1); return pop; } //确定索引i对应的data[i]是堆中的元素 bool contain(int i) { assert(i>=0 && i + 1 <= capacity); //用户以为是从0索引的，故i+1 return reverse[i + 1] != 0; } //用户已知某个元素的索引，返回这个索引对应的值，用户以为是从0索引的，故i+1 Item getItem(int i) { //确定i对应的data[i]是堆中的元素 assert(contain(i)); return data[i + 1]; } //用户更换索引i的值，用户以为是从0索引的，故i+1 void change(int i, Item newItem) { //确定i对应的data[i]是堆中的元素，且reverse才有用 assert(contain(i)); i = i + 1; data[i] = newItem; //找到indexes[j]=i;j表示data[i]在堆中位置 //之后shiftup(j),再shifedown(j) int j = reverse[i]; shiftUp(j); shiftDown(j); }};//两种构造函数，两种测试代码//-------------------索引堆的调试程序（--------------------IndexMaxHeapindexmaxheap = IndexMaxHeap(50);cout << "indexmaxheap size:" << indexmaxheap.size() << endl;srand(time(NULL));for (int heap_i = 0; heap_i < 50; heap_i++){ indexmaxheap.Insert(heap_i, rand()%51);}cout << "indexmaxheap size:" << indexmaxheap.size() << endl;indexmaxheap.change(10, 100);//cout << indexmaxheap.getItem(10) << " ";while (!indexmaxheap.isEmpty()){ cout << indexmaxheap.extractMax() << " "; //提取最大值的索引，也会提出数据 //cout<< indexmaxheap.extractMaxIndex() << endl;}//测试代码void indexmaxheap(int arr[], int n){ IndexMaxHeapindexmaxheap = IndexMaxHeap(arr, n); while (!indexmaxheap.isEmpty()) { cout << indexmaxheap.extractMax() << endl; }}

延深：

实现：用最小堆来实现，先取100个元素组成堆，再将后面的元素一个一个跟堆中最小的元素相比较，如大于最小的元素，提取出最小堆的最小值，将该元素加入堆中，最后保留的，就是N个元素中前100名。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。