voidInsert(ElementTypeX,PriorityQueueH){inti;if(IsFull(H)){printf("Queue is full.\n");return;}for(i=++H->Size;H->Element[i/2]>X;i/=2)H->Elements[i]=H->Elements[i/2];H->Elements[i]=X;}
ElementTypeDeleteMin(PriorityQueueH){inti,Child;ElementTypeMinElement,LastElement;if(IsEmpty(H)){printf("Queue is empty.\n");returnH->Elements[0];}MinElement=H->Elements[1];LastElement=H->Elements[H->Size--];for(i=1;i*2<=H->Size;i=Child){// Find smaller child.Child=i*2;if(Child!=H->Size&&H->Elements[Child+1]<H->Elements[Child])Child++;// Percolate one level.if(LastElement>H->Elements[Child])H->Elements[i]=H->Elements[Child];elsebreak;}H->Elements[i]=LastElement;returnMinElement;}
堆積, 關於地理學的, 請見作用, 關於名稱相近的資料結構, 請見堆栈, stack, heap, 是计算机科学中的一種特別的完全二叉树, 若是滿足以下特性, 即可稱為, 給定中任意節點p和c, 若p是c的母節點, 那麼p的值會小於等於, 或大於等於, c的值, 若母節點的值恆小於等於子節點的值, 此稱為最小, heap, 反之, 若母節點的值恆大於等於子節點的值, 此稱為最大, heap, 在中最頂端的那一個節點, 稱作根節點, root, node, 根節點本身沒有母節點, parent, node, 的各地常. 關於地理學的堆積 請見堆積作用 關於名稱相近的資料結構 請見堆栈 Stack 堆 Heap 是计算机科学中的一種特別的完全二叉树 若是滿足以下特性 即可稱為堆積 給定堆積中任意節點P和C 若P是C的母節點 那麼P的值會小於等於 或大於等於 C的值 若母節點的值恆小於等於子節點的值 此堆積稱為最小堆積 min heap 反之 若母節點的值恆大於等於子節點的值 此堆積稱為最大堆積 max heap 在堆積中最頂端的那一個節點 稱作根節點 root node 根節點本身沒有母節點 parent node 堆積 的各地常用別名中国大陸堆港臺堆積堆積始於J W J Williams 英语 J W J Williams 在1964年發表的堆積排序 heap sort 當時他提出了二元堆積樹作為此演算法的資料結構 目录 1 性质 2 支持的基本操作 3 示例代码 4 应用 4 1 堆排序 4 2 事件模拟 4 3 優先權佇列 4 4 戴克斯特拉演算法 5 参考 6 参见性质 编辑堆的实现通过构造二叉堆 binary heap 实为二叉树的一种 由于其应用的普遍性 当不加限定时 均指该数据结构的这种实现 这种数据结构具有以下性质 任意节点小于 或大于 它的所有后裔 最小元 或最大元 在堆的根上 堆序性 堆总是一棵完全树 即除了最底层 其他层的节点都被元素填满 且最底层尽可能地从左到右填入 将根节点最大的堆叫做最大堆或大根堆 根节点最小的堆叫做最小堆或小根堆 堆有許多種進階類型包含了適合製作雙端佇列的最大 最小堆積及製作優先權佇列的斐波那契堆積等 支持的基本操作 编辑操作 描述 时间复杂度build 採用羅伯特 弗洛伊德提出的較快方式建立堆 O n displaystyle O n nbsp insert 向堆中插入一个新元素 O log n displaystyle O log n nbsp update 将新元素提升使其符合堆的性质 O log n displaystyle O log n nbsp get 获取当前堆顶元素的值 O 1 displaystyle O 1 nbsp delete 删除堆顶元素 O log n displaystyle O log n nbsp heapify 使删除堆顶元素的堆再次成为堆 O log n displaystyle O log n nbsp 某些堆实现还支持其他的一些操作 如斐波那契堆支持检查一个堆中是否存在某个元素 示例代码 编辑为将元素X插入堆中 找到空闲位置 建立一个空穴 若满足堆序性 英文 heap order 则插入完成 否则将父节点元素装入空穴 删除该父节点元素 完成空穴上移 直至满足堆序性 这种策略叫做上滤 percolate up 1 void Insert ElementType X PriorityQueue H int i if IsFull H printf Queue is full n return for i H gt Size H gt Element i 2 gt X i 2 H gt Elements i H gt Elements i 2 H gt Elements i X 以上是插入到一个二叉堆的过程 DeleteMin 删除最小元 即二叉树的根或父节点 删除该节点元素后 队列最后一个元素必须移动到堆得某个位置 使得堆仍然满足堆序性质 这种向下替换元素的过程叫作下滤 ElementType DeleteMin PriorityQueue H int i Child ElementType MinElement LastElement if IsEmpty H printf Queue is empty n return H gt Elements 0 MinElement H gt Elements 1 LastElement H gt Elements H gt Size for i 1 i 2 lt H gt Size i Child Find smaller child Child i 2 if Child H gt Size amp amp H gt Elements Child 1 lt H gt Elements Child Child Percolate one level if LastElement gt H gt Elements Child H gt Elements i H gt Elements Child else break H gt Elements i LastElement return MinElement 应用 编辑堆排序 编辑 主条目 堆排序 堆 通常是二叉堆 常用于排序 这种算法称作堆排序 事件模拟 编辑 主要运用堆的排序以选择优先 優先權佇列 编辑 在队列中 调度程序反复提取队列中第一个作业并运行 因为实际情况中某些时间较短的任务将等待很长时间才能结束 或者某些不短小 但具有重要性的作业 同样应当具有优先权 堆即为解决此类问题设计的最佳数据结构 1 戴克斯特拉演算法 编辑 在戴克斯特拉演算法中使用斐波那契堆積或二元堆可使得佇列的操作更為快速 参考 编辑 1 0 1 1 数据结构与算法分析 Mark Allen Weiss 美 第六章 优先队列 堆 参见 编辑二叉堆 二项式堆 最小 最大堆 斐波纳契堆 数据结构 取自 https zh wikipedia org w index php title 堆積 amp oldid 75802176, 维基百科,wiki,书籍,书籍,图书馆,