数据结构-堆（程序）

谁借莪１个温暖的怀抱￠ 2022-05-27 05:39 138阅读 0赞

用程序实现：

（1）根据一个数组建立大根堆（最大堆）；

（2）插入数据，向上调整为大根堆；

（3）删除根节点数据，重新调整为大根堆；

（4）堆排序

程序如下：

#include<iostream>
    #include<assert.h>
    //#include"List.h"
    #include<string>
    //#include"Stack.h"
    //#include"Tree.h"
    
    #define MAX 100
    using namespace std;
    
    //根据数据创建堆
    void CreateHeap(int *heap, int length);
    //向下调整堆中元素
    void AdjustDownHeap(int *heap, int i, int length);
    //向上调整堆中元素
    void AdjustUpHeap(int *heap, int i, int length);
    //向堆中插入元素
    int InsertHeap(int *heap, int length, int x);
    //删除元素，每次只能删除根节点
    int DeleteHeap(int *heap, int length);
    //堆排序
    void SortHeap(int *heap, int length);
    int main()
    {
    	int heap[7] = {4,5,6,9,8,7};
    	printf("根据所给数组元素创建大根堆：");
    	CreateHeap(heap,6);
    	for (int i = 0; i < 6;i++)
    	{
    		printf("%d ",heap[i]);
    	}
    	printf("\n");
    	printf("插入元素10，向上调整：");
    	InsertHeap(heap,6,10);
    	for (int i = 0; i < 7; i++)
    	{
    		printf("%d ", heap[i]);
    	}
    	printf("\n");
    	printf("删除根节点，调整为大根堆：");
    	DeleteHeap(heap, 7);
    	for (int i = 0; i < 6; i++)
    	{
    		printf("%d ", heap[i]);
    	}
    	printf("\n");
    	printf("根据大根堆进行堆排序：");
    	SortHeap(heap, 6);
    	for (int i = 0; i < 6; i++)
    	{
    		printf("%d ", heap[i]);
    	}
    	printf("\n");
    	return 0;
    }
    
    //根据数据创建堆，用数组创建堆
    void CreateHeap(int *heap,int length)
    {
    	//向下调整创建大根堆
    	for (int i = length / 2-1; i >= 0;i--)
    	{
    		AdjustDownHeap(heap, i, length);
    	}
    }
    
    //向下调整堆中元素
    void AdjustDownHeap(int *heap,int i,int length)
    {
    	int temp = 0;
    	int nChild;
    	while ((2 * i + 1)<length)
    	{
    		nChild = 2 * i + 1;
    		//当存在左右儿子节点时，判断左儿子节点和右儿子节点大小关系
    		if (heap[nChild]<heap[nChild + 1] && nChild+1<length)
    		{
    			nChild++;
    		}
    		if (heap[i]<heap[nChild])
    		{
    			temp = heap[i];
    			heap[i] = heap[nChild];
    			heap[nChild] = temp;
    			i = nChild;
    		}
    		else
    		{
    			break;
    		}
    	}
    }
    
    //向堆中插入元素，将元素插入到堆最后位置，再向上调整
    int InsertHeap(int *heap,int length,int x)
    {
    	int i = length;
    	int temp = 0;
    	heap[length] = x;
    	while (i>0)
    	{
    		if (heap[i]>heap[(i-1)/2])
    		{
    			temp = heap[i];
    			heap[i] = heap[(i - 1) / 2];
    			heap[(i - 1) / 2] = temp;
    			i = (i-1) / 2;
    		}
    		else
    		{
    			break;
    		}
    	}
    	//返回插入位置
    	return i;
    }
    //删除元素，只能删除根节点；将根节点换成堆最后一个元素，删除根节点，然后再向下调整使之变成大根堆
    int DeleteHeap(int *heap, int length)
    {
    	int topNum = heap[0];
    	heap[0] = heap[length-1];
    	AdjustDownHeap(heap,0,length-1);
    	//返回根节点元素
    	return topNum;
    }
    //堆排序
    void SortHeap(int *heap, int length)
    {
    	int index = length - 1;
    	int temp = 0;
    	int num = 0;
    	while (index > 0)
    	{
    		temp = heap[0];
    		heap[0] = heap[index];
    		heap[index] = temp;
    		AdjustDownHeap(heap, 0, index);
    		index--;
    	}
    
    }

![20180412154901832][]

[20180412154901832]: /images/20220527/4f21028da55145848668e0761e5267d7.png