首页 > 代码库 > 数据结构--左式堆的思想和代码

数据结构--左式堆的思想和代码

      左式堆也是实现优先列队的一种数据结构,和二叉堆一样,左式堆也具有堆序性和结构性。

 

      堆序性: 一个节点的后裔都大于等于这个节点。

 

      结构性:左式堆也是二叉树,和二叉堆的唯一区别在于左式堆不是理想平衡的,实际上是趋于非常不平衡,对于堆中每一个节点X,左儿子的零路径长至少与右儿子的零路径长一样大,零路径长Npl的定义为:节点到一个没有两个儿子的节点的最短路径长,因此具有0个或者1个儿子节点的Npl为0,Npl(NULL) = -1。

 

     左式堆可以高效的支持合并操作,而插入和删除操作都可以通过合并操作来实现,相关的代码如下:

 

#include<iostream>

using namespace std;

struct TreeNode;
typedef struct TreeNode *PriorityQueue;

PriorityQueue Init(void);
int FindMin(PriorityQueue H);
bool IsEmpty (PriorityQueue H);
PriorityQueue Merge(PriorityQueue H1,PriorityQueue H2);  //合并操作

#define Insert(x,H) (H = Insert1(x,H))

PriorityQueue Insert1 (int x,PriorityQueue H);
PriorityQueue DeleteMin1(PriorityQueue H);

struct TreeNode
{
   int Element;
   PriorityQueue Left;
   PriorityQueue Right;
   int Npl;   //零路径长,节点X到一个没有两个儿子的节点的最短路径的长
};

static void SwapChildren (PriorityQueue H)   //交换根节点的左右子树
{
  PriorityQueue temp;
  temp = H->Right;
  H->Right = H->Left;
  H->Left = temp;
}
static PriorityQueue Merge1(PriorityQueue H1,PriorityQueue H2)
{
   if(H1->Left == NULL)  //H1为单点,就一个元素
	   H1->Left = H2;
   else
   {
      H1->Right = Merge(H1->Right,H2);
	  if(H1->Left->Npl < H1->Right->Npl)
		  SwapChildren(H1);
	  H1->Npl = H1->Right->Npl + 1;
   }
   return H1;
}

PriorityQueue Merge(PriorityQueue H1,PriorityQueue H2)     //处理特殊情况 
{
   if(H1 == NULL)
	   return H2;
   if(H2 == NULL)
	   return H1;
   if(H1->Element < H2->Element )
	   return Merge1(H1,H2);
   else
	   return Merge1(H2,H1);
}


PriorityQueue Insert1(int x,PriorityQueue H)   //把x看成但节点,执行合并操作,思想很巧妙
{
   PriorityQueue SingleNode;
   SingleNode = (PriorityQueue)malloc(sizeof(struct TreeNode));
   if(SingleNode == NULL) cout << "out of space" << endl;
   else
   {
      SingleNode->Element = x;
	  SingleNode->Left = NULL;
	  SingleNode->Npl = 0;
	  SingleNode->Right = NULL;
	  H = Merge(SingleNode, H);
   }
   return H;
}

bool IsEmpty(PriorityQueue H)
{
     if(H == NULL)
		 return true;
	 else
		 return false;
}

PriorityQueue DeleteMin(PriorityQueue H)    //删除操作,因为左式堆的堆序性,最小值就在根处,因此删除操作直接就是把根的左子树和右子树合并即可
{
   PriorityQueue LeftHeap,RightHeap;
   if(IsEmpty(H))
   {
      cout << "Priority queue is Empty" << endl;
	  return H;
   }
   LeftHeap = H->Left;
   RightHeap = H->Right;
   free(H);
   return Merge(LeftHeap,RightHeap);
}

int main ()
{


   return 0;
}

   插入和删除操作都可以通过合并操作来实现,这种思想很巧妙,值得我们学习。

 

    夜深了,,,

 

   网易云的歌单循环到了《愿得一人心》这首钢琴曲,音乐都是有灵魂的,只愿得一人心,白首不分离。

     

数据结构--左式堆的思想和代码