殷书数据结构5.8——堆

最小堆实现:MinHeap.h

#include 
using namespace std;  
#define DefaultSize 10

template
class MinHeap {
public:
	MinHeap(int sz = DefaultSize);	//构造函数：建立空堆
	MinHeap(E arr[], int n);		//构造函数：通过一个数组创建堆
	~MinHeap() { delete[] heap; }	//析构函数
	bool insert(const E& x);		//将x插入到最小堆中
	bool removeMin(E& x);			//删除堆顶元素(min value)
	void HeapSort();
	bool isEmpty() const{
		return (currentSize==0) ? true : false;
	}			//判断堆是否是空
	bool isFull() const{
		return (currentSize==maxHeapSize) ? true : false;
	}			//判断堆是否已满
	void makeEmpty(){
		currentSize=0;
	}			//置空堆 
	void output(){
		for (int i = 0; i < currentSize; i ++) 
			std::cout << heap[i] << ' ';   //数组元素输出
	}	
private:
	E* heap;						//存放最小堆元素的数组
	int currentSize;				//最小堆中当前元素的个数
	int maxHeapSize;				//最小堆最多存放元素个数
	void siftDown(int start, int m);//从start到m下滑调整为最小堆
	void siftUp(int start);			//从start到0上滑调整为最小堆
};

//函数定义
template
MinHeap::MinHeap(int sz) {
	//方式1建立最小堆，动态创建
	maxHeapSize = (DefaultSize < sz) ? sz : DefaultSize;
	heap = new E[maxHeapSize];
	if (nullptr == heap) {
		std::cerr << "内存分配失败" << std::endl;
		exit(EXIT_FAILURE);
	}
	currentSize = 0;
}

template
MinHeap::MinHeap(E arr[], int n) {
	//方式2创建最小堆，从已知数组中复制数据，然后调整为最小堆结构
	//函数参数：已知数组数据、数据个数
	maxHeapSize = (DefaultSize < n) ? n : DefaultSize;
	heap = new E[maxHeapSize];
	if (nullptr == heap) {
		std::cerr << "内存分配失败" << std::endl;
		exit(EXIT_FAILURE);
	}
	for (int i = 0; i < n; i ++) {
		heap[i] = arr[i];							//数据copy
	}
	currentSize = n;
	//利用完全二叉树中元素的排列规律，找到最初调整位置，也就是最后的分支节点
	int currentPos = (currentSize - 1) / 2;			
	while (currentPos >= 0)	{						//自底向上逐步扩大形成堆
		siftDown(currentPos, currentSize - 1);		//局部调整
		currentPos--;								//向前换一个分支节点
	}
}
template
bool MinHeap::insert(const E& x) {
	//共有函数：将x插入到最小堆中
	if (isFull()) {									//判断堆是否已经满
		std::cerr << "Heap Fulled" << std::endl;
		return false;								
	}
	heap[currentSize] = x;							//将x元素插入到数组最后
	siftUp(currentSize);							//堆排序，从大到小 
	currentSize++;									//对当前大小增加1
	return true;
}

template
bool MinHeap::removeMin(E& x) {
	//删除堆顶元素，引用返回
	if (0 == currentSize) {
		std::cout << "Heap Emptyed" << std::endl;
		return false;
	}
	x = heap[0];
	heap[0] = heap[currentSize - 1];
	currentSize--;
	siftDown(0, currentSize - 1);					//借助函数对堆再一次调整
	return true;
}

template
void MinHeap::siftDown(int start, int m) {
	//私有函数：从节点start开始到m为止，自上向下比较，如果子女值小于父节点的值，
	//则关键码小的上浮，继续向下层比较，这样将一个集合的局部调整为最小堆
	int i = start;
	int j = 2 * i + 1;								//通过公式2x+1求得x左子女位置
	E temp = heap[i];								//temp记录原来的的数据
	while (j <= m) {
		if (j < m && heap[j] > heap[j + 1]) {
			j = j + 1;								//j指向左右子女中较小的一个
		}
		if (heap[j] >= temp) {
			break;									//已经符合最小堆的结构，无需调整
		}
		else {										//否则调整，并更新i，j至下一层
			heap[i] = heap[j];						
			i = j;
			j = 2 * i + 1;
		}
	}
	heap[i] = temp;									//完成调整后的数据交换
}

template
void MinHeap::siftUp(int start) {
	//私有函数：从节点start开始到节点0为止，自下向上比较，如果子女的值小于父节点的值
	//则相互交换，这样讲集合重新调整为最小堆(注意比较元素E的逻辑运算符重载)
	int j = start;
	int i = (j - 1) / 2;								//找左子女公式的逆运算公式
	E temp = heap[j];
	while (j > 0) {
		if (heap[i] <= temp) {
			break;
		}
		else {
			heap[j] = heap[i];
			j = i;
			i = (j - 1) / 2;
		}
	}
	heap[j] = temp;
}


//堆排序，从大到小
template
void MinHeap::HeapSort(){
	int len=currentSize;
	for(int i=len-1;i>=0;i--){
		swap(heap[0],heap[i]);
		siftDown(0,i-1);
	}
} 

主函数main.cpp

#include
#include"MinHeap.h"
using namespace std; 

int main()
{
	int data[8] {0};
	
	//用数组数据建最小堆测试
	for (int i = 0; i < 8; i ++) {
		cin >> data[i];
	}
	MinHeap minheap(data, 8);
	minheap.output();
	cout << endl;

	//向堆内插入元素测试
	int value{11};
	minheap.insert(value);
	minheap.output();
	cout << endl;

	//从堆内删除元素测试
	int delValue{ 0 };
	minheap.removeMin(delValue);
	minheap.output();
	cout << endl;
	minheap.HeapSort();
	minheap.output();
	return 0;
}

堆的应用：
1.堆排序：

借助上面写好的堆数据实现
template
void MinHeap::HeapSort(){
	int len=currentSize;
	for(int i=len-1;i>=0;i--){
		swap(heap[0],heap[i]);
		siftDown(0,i-1);
	}
}

简单版本(堆调整、建堆、堆排序)
#include
using namespace std;

void heapify(int *arr,int i,int n){
	if(i>=n) return;
	int l=2*i+1,r=2*i+2,large=i;
	if(larr[large]){
		large=l; 
	}
	if(rarr[large]){
		large=r;
	}
	if(large!=i){
		swap(arr[i],arr[large]);
		heapify(arr,large,n); 
	}
}

void build_heap(int *arr,int n){
	for(int i=(n-2)/2;i>=0;i--){
		heapify(arr,i,n);
	}
}

//堆排序, 
void HeapSort(int *arr,int n){
	build_heap(arr,n);
	for(int i=n-1;i>=0;--i){
		swap(arr[i],arr[0]);
		heapify(arr,0,i-1);   
	}
}

int main(){
	int n;
	cin>>n;
    int arr[n];  
    for (int i=0;i
        cin >> arr[i];  
	}
	HeapSort(arr,n);
	for (int i = 0; i < n; ++i) {
        cout << arr[i]<< " "; 
    }
    return 0;
}

2.堆中第k大元素(黄宇算法设计与分析习题14.2)

#include
using namespace std;

void heapify(int *arr,int i,int n){
	if(i>=n) return;
	int l=2*i+1,r=2*i+2,large=i;
	if(larr[large]){
		large=l; 
	}
	if(rarr[large]){
		large=r;
	}
	if(large!=i){
		swap(arr[i],arr[large]);
		heapify(arr,large,n); 
	}
}

void build_heap(int *arr,int n){
	for(int i=(n-2)/2;i>=0;i--){
		heapify(arr,i,n);
	}
}

//堆中第k大元素 
int findKthLargest(int *arr,int n,int k){
	build_heap(arr,n);
	for(int i=n-1;i>=n-k+1;--i){
		swap(arr[i],arr[0]);
		heapify(arr,0,i-1);   
	}
	return arr[0];
}

int main(){
	int n,k;
	cin>>n;
    int arr[n];  
    for (int i=0;i
        cin >> arr[i];  
	}
	cin>>k;
	cout<