优先队列---二叉堆-白红宇

优先队列---二叉堆

阅读量：4046 次

发布时间：2019-05-25

本文共 2424 字，大约阅读时间需要 8 分钟。

优先队列---二叉堆：

二叉堆是一棵完全二叉树，最大堆（最小堆）中，所有根节点的键值都要比对应的子树要大（小）。

由于是完全二叉树，所以存储结构可以采用数组。

最大堆的创建：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define INF 0x3f3f3f3ftypedef int ElementType;using namespace std;struct HeapNode { ElementType *Elements; int Size;//当前个数 int Capacity;//最大容量};typedef struct HeapNode *MaxHeap;MaxHeap Create(int MaxSize){ MaxHeap H = (MaxHeap)malloc(sizeof(struct HeapNode)); H->Elements = (ElementType*)((MaxSize + 1) * sizeof(ElementType)); H->Size = 0; H->Capacity = MaxSize; H->Elements[0] = INF;//哨兵 return H;}

最大堆的插入：

思想：先把待查元素放在数组的最后一个位置，然后和它的父亲去比较大小，如果比他父亲节点值大，则和它父亲互换，然后再依次和父亲节点比较大小，直到比父亲节点值小为止。为了减少互换的操作，可以先去找到最后待查元素的位置再去放（这样就有一个空穴）。---这一策略叫做上滤（空穴往上走）

数组0处放哨兵，卡住边界。

void Insert(MaxHeap H, ElementType item){	if (H->Size >= H->Capacity)	{		cout << "满" << endl; return;	}	int i = ++H->Size;	for (; H->Elements[i / 2] < item; i /= 2)//0处有哨兵。		H->Elements[i] = H->Elements[i / 2];//上面的往下面走。直到i的父节点中的值大于item。	H->Elements[i] = item;//放}

最大堆的删除：

思想：把根节点元素返回。数组最后一个元素（tmp）先放在根节点位置（1位置），然后再去调整堆的顺序性，类似于插入，根节点元素值和儿子节点最大值相比较，如果前者比后者小，就互换，依次互换下去，直到tmp大于两个儿子节点的大小位置。

为了减少互换的操作，同样可以先找到tmp最后放的位置，由于这次空穴往下走，所以该策略叫做下滤。

ElementType DeleteMax(MaxHeap H){	int parent, child;	ElementType maxitem, tem;	if (H->Size == 0) { cout << "空" << endl; return; }	maxitem = H->Elements[1];//最大值，便于后面返回。	tem = H->Elements[H->Size--];	for (parent = 1; parent * 2 <= H->Size; parent = child)	{		child = parent * 2;		if (child != H->Size&&H->Elements[child] < H->Elements[child + 1])			child++;		if (tem >= H->Elements[child])break;		else H->Elements[parent] = H->Elements[child];//下面的往上走，直到遇到tem大于下面的两个儿子为止。	}	H->Elements[parent] = tem;//放	return maxitem;}

最大堆的建立：

方法1：通过插入操作，依次将N个元素插入一个初始化为空的堆中。时间复杂度为O（NlogN）。

方法2：先将N个元素按输入顺序存入数组，然后调整各个节点的位置，以满足最大堆的有序性。

调整办法：从倒数第一个有儿子的节点开始依次调整，这样就能保证下面的堆序。类似于删除的操作，每次将要调整的子堆根节点拿出来，然后下滤，找到根节点的位置，放入即可。

这种方法的时间复杂度为是N。

void PercDown(MaxHeap H ,int p ){	int Parent, Child;	ElementType X;	X  = H->Elements[p];	for (Parent = p; Parent * 2 <= H->Size; Parent = Child )	{		Child  = Parent  * 2;		if ((Child != H->Size) && (H->Elements[Child]
   
    Elements[Child + 1]))			Child++;	   		if (X  >= H->Elements[Child]) break;    		else   			H->Elements[Parent] = H->Elements[Child];	}	H->Elements[Parent] = X;}void BuildHeap(MaxHeap H ){	 int i;	  for (i  = H->Size / 2; i>0; i--)        		  PercDown(H, i );}

转载地址：http://muyci.baihongyu.com/

你可能感兴趣的文章