数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究C++ 程序实现堆排序
堆是一个完全二叉树，它要么是 Min 堆，要么是 Max 堆。在 Max 堆中，根上的键在 Heap 中存在的所有键之中必须最大。此属性必须对该二叉树中的所有节点递归成立。Min 堆类似于 MinHeap。
函数说明
void BHeap::Insert(int ele): 执行插入操作以向堆中插入元素。
void BHeap::DeleteMin(): 执行删除操作以从堆中删除最小值。
int BHeap::ExtractMin(): 执行操作以从堆中提取最小值。
void BHeap::showHeap(): 显示堆中的元素。
void BHeap::heapifyup(int in): 从下往上维护堆结构。
void BHeap::heapifydown(int in): 从上往下维护堆结构。
示例
#include <iostream>
#include <cstdlib>
#include <vector>
#include <iterator>
using namespace std;
class BHeap {
private:
vector <int> heap;
int l(int parent);
int r(int parent);
int par(int child);
void heapifyup(int in);
void heapifydown(int in);
public:
BHeap()
{}
void Insert(int element);
void DeleteMin();
int ExtractMin();
void showHeap();
int Size();
};
int main() {
BHeap h;
while (1) {
cout<<"1.Insert Element"<<endl;
cout<<"2.Delete Minimum Element"<<endl;
cout<<"3.Extract Minimum Element"<<endl;
cout<<"4.Show Heap"<<endl;
cout<<"5.Exit"<<endl;
int c, e;
cout<<"Enter your choice: ";
cin>>c;
switch(c) {
case 1:
cout<<"Enter the element to be inserted: ";
cin>>e;
h.Insert(e);
break;
case 2:
h.DeleteMin();
break;
case 3:
if (h.ExtractMin() == -1) {
cout<<"Heap is Empty"<<endl;
}
else
cout<<"Minimum Element: "<<h.ExtractMin()<<endl;
break;
case 4:
cout<<"Displaying elements of Hwap: ";
h.showHeap();
break;
case 5:
exit(1);
default:
cout<<"Enter Correct Choice"<<endl;
}
}
return 0;
}
int BHeap::Size() //size of heap {
return heap.size();
}
void BHeap::Insert(int ele) //insert element in heap {
heap.push_back(ele);//push element into the heap
heapifyup(heap.size() -1);//call heapifyup() to maintain heap structure
}
void BHeap::DeleteMin() //delete minimum value from heap {
if (heap.size() == 0) {
cout<<"Heap is Empty"<<endl;
return;
}
heap[0] = heap.at(heap.size() - 1);
heap.pop_back();//pop element
heapifydown(0);
cout<<"Element Deleted"<<endl;
}
int BHeap::ExtractMin() //extract minimum value from heap
{
if (heap.size() == 0) {
return -1;
}
else
return heap.front();
}
void BHeap::showHeap() //show the elements of heap {
vector <int>::iterator pos = heap.begin();
cout<<"Heap --> ";
while (pos != heap.end()) {
cout<<*pos<<" ";
pos++;
}
cout<<endl;
}
int BHeap::l(int parent) // return left child of node.
{
int l = 2 * parent + 1;
if (l < heap.size())
return l;
else
return -1;
}
int BHeap::r(int parent) // return right child of node.
{
int r = 2 * parent + 2;
if (r < heap.size())
return r;
else
return -1;
}
int BHeap::par(int child)// return parent
{
int p = (child - 1)/2;
if (child == 0)
return -1;
else
return p;
}
void BHeap::heapifyup(int in)//maintain heap structure in bottom up manner.
{
if (in >= 0 && par(in) >= 0 && heap[par(in)] > heap[in]) {
int temp = heap[in];
heap[in] = heap[par(in)];
heap[par(in)] = temp;
heapifyup(par(in));
}
}
void BHeap::heapifydown(int in)//maintain heap structure in top down manner.
{
int child = l(in);
int child1 = r(in);
if (child >= 0 && child1 >= 0 && heap[child] > heap[child1]) {
child = child1;
}
if (child > 0 && heap[in] > heap[child]) {
int t = heap[in];
heap[in] = heap[child];
heap[child] = t;
heapifydown(child);
}
}输出
1.Insert Element 2.Delete Minimum Element 3.Extract Minimum Element 4.Show Heap 5.Exit Enter your choice: 1 Enter the element to be inserted: 2 1.Insert Element 2.Delete Minimum Element 3.Extract Minimum Element 4.Show Heap 5.Exit Enter your choice: 1 Enter the element to be inserted: 3 1.Insert Element 2.Delete Minimum Element 3.Extract Minimum Element 4.Show Heap 5.Exit Enter your choice: 1 Enter the element to be inserted: 7 1.Insert Element 2.Delete Minimum Element 3.Extract Minimum Element 4.Show Heap 5.Exit Enter your choice: 1 Enter the element to be inserted: 6 1.Insert Element 2.Delete Minimum Element 3.Extract Minimum Element 4.Show Heap 5.Exit Enter your choice: 4 Displaying elements of Hwap: Heap --> 2 3 7 6 1.Insert Element 2.Delete Minimum Element 3.Extract Minimum Element 4.Show Heap 5.Exit Enter your choice: 3 Minimum Element: 2 1.Insert Element 2.Delete Minimum Element 3.Extract Minimum Element 4.Show Heap 5.Exit Enter your choice: 3 Minimum Element: 2 1.Insert Element 2.Delete Minimum Element 3.Extract Minimum Element 4.Show Heap 5.Exit Enter your choice: 2 Element Deleted 1.Insert Element 2.Delete Minimum Element 3.Extract Minimum Element 4.Show Heap 5.Exit Enter your choice: 4 Displaying elements of Hwap: Heap --> 3 6 7 1.Insert Element 2.Delete Minimum Element 3.Extract Minimum Element 4.Show Heap 5.Exit Enter your choice: 5
更新于: 2019 年 7 月 30 日
695 次浏览
广告