堆（C语言） |
您所在的位置：网站首页 › c语言中的二叉树是什么 › 堆（C语言） |
堆（C语言）
|
数组表示的完全二叉树 数组下标为0的位置放一个比所有堆中元素都要小的元素（可以是ElementType的最小值），称为“哨兵”。从下标为1的位置开始存放堆中元素。因为是完全二叉树，所以父亲节点与其左右子节点下标满足一些关系。 例： 存储结构 typedef struct HeapStruct{ ElementType *Element; /* 存储堆元素的数组 */ int Size; /* 堆的当前元素个数（最后一个元素的下标） */ int MaxSize; /* 堆存储空间的大小 */ }HeapStruct,*MinHeap;操作集的实现 MinHeap Create(int MaxSize): 创建一个空的最小堆 MinHeap Create(int MaxSize) { MinHeap H = (MinHeap)malloc(sizeof(struct HeapStruct));//分配堆结构空间 H->Elenment = (ElementType *)malloc((MaxSize + 1) * sizeof(ElementType));//分配储存堆元素的数组的空间 H->Size = 0; H->MaxSize=MaxSize; H->Elenment[0] = INT_MIN;//数组第一个元数放最小元素，数组第二个元素放堆中最小元素 return H; }void Destroy(MinHeap H): 释放堆申请的空间 void Destroy(MinHeap H) { free(H->Elenment);//先释放堆节点的数组空间 free(H);//再释放堆节点的空间 }boolean IsFull(MinHeap H): 判断最小堆是否已满 boolean IsFull(MinHeap H) { return (H->Size == H->MaxSize);//判断最小堆中元素个数Size是否等于最大容量MAXSIZE。 }boolean IsEmpty(MinHeap H): 判断最小堆是否为空 boolean IsEmpty(MinHeap H) { return (H->Size == 0);//判断堆中元素个数是否等于0 }void Insert(MinHeap H,ElementType item): 将元素item插入最小堆H //将元素item插入堆H void Insert(MinHeap H, ElementType item) { int i = 0; //判断堆H是否已满 if (IsFull(H)) { printf("Heap is full\n"); return; } /* 如果H未满，将item放入堆最后一个元素，查看它的父节点，如果它的父节点比它大，将它和它的父节点互换位置， 循环此过程，直至它的父节点小于它。可能它比所有它的父节点都要小，但是一定会比哨兵大（数组中下标为0的位置）， 所以一定最后它的下标一定大于哨兵的下标0。这就是哨兵的意义。 */ H->Size++; for (i = H->Size; H->Element[i / 2] > item; i = i / 2) { H->Element[i] = H->Element[i / 2]; } H->Element[i] = item; }ElementType Delete(MinHeap H): 返回最小堆H中最小元素（高优先级） //将堆根节点元素取出，并将堆元素重新排序 ElementType Delete(MinHeap H) { int parent=0,child=0; ElementType item,temp; //判断堆是否已经空了 if (IsEmpty(H)) { printf("Heap is Empty\n"); return H->Element[0]; } /* 堆没有空，将根节点返回，最后一个叶子节点放到根节点位置，然后比较它与它的左右子节点中最小 节点的大小，如果它比较大，则将它和它的较小的子节点互换位置，重复此过程，直至他比两个子节点 都小或者它不在有子节点 */ item = H->Element[1]; temp = H->Element[H->Size]; H->Size--; for (parent = 1; parent *2 Size; parent = child) { child = parent *2; //找出左右子节点最小的那个 if (child != H->Size && (H->Element[child] > H->Element[child + 1])) { child++; } //比较它与最小的子节点的大小，如果它比较大，则两者互换位置，否则跳出循环 if (temp > H->Element[child]) { H->Element[parent] = H->Element[child]; } else { break; } } H->Element[parent] = temp; return item; }MinHeap BuildMinHeap(ElementType *Elenment, int Size): 创建一个非空的堆 已知堆中元素，但是不知道其在数组中的排列顺序，可以有两种创建堆的方法：一是先创建一个空堆，再使用Insert()函数将元素一个个插入堆中。二是直接将数组复制到堆节点的Element数组中，然后进行排序。 第二种方法比第一种方法时间复杂度更低。 //已知一个数组，创建一个由数组元素组成的最小堆 MinHeap BuildMinHeap(ElementType *Element, int Size,int MaxSize) { MinHeap H = NULL; int i = 0, parent = 0, child = 0; ElementType Temp; //创建一个空最小堆 H = CreateMinHeap(MaxSize); //判断存储空间是否够用 if (Size > H->MaxSize) { printf("最小堆存储空间不足，建立最小堆失败\n"); return NULL; } //将数组中元素复制到存储最小堆元素的数组里 for (i = 0; i Element[i + 1] = Element[i]; } H->Size = Size; //给最小堆存储空间中元素排序 /* 最后一个节点的父节点的左右指针都指向一个堆，将最后一个节点的父节点和它的两个子节点排序（方法类似 与删除节点的操作），使得最后一个节点、其父节点和其兄弟节点形成一个堆。循环操作，从最后一个节点的 父节点往上依次执行这个操作，最后使得整个树都是一个堆。 */ for (parent = H->Size / 2; parent >= 1; parent--) { Temp = H->Element[parent]; for (; parent * 2 Size; parent = child) { child = parent * 2;//child为parent左子树的下标，(child+1)为右子树下标 //如果左右子树都存在，且左子树大于右子树的值，将child作为两者较小者的下标 if (child != H->Size && (H->Element[child] > H->Element[child + 1])) { child++; } //比较parent指向的节点与child指向节点的大小，parent较大则两者互换位置 if (Temp > H->Element[child]) { H->Element[parent] = H->Element[child]; } else { break; } } H->Element[parent] = Temp; } return H; } |
由子节点找父节点：父节点下标=子节点下标 / 2 由父节点找左子节点：左子节点下标=父节点下标 * 2 由父节点找右子节点：右子节点下标=父节点下标 * 2 + 1【本文地址】
今日新闻 |
推荐新闻 |