flforever1213
- 浏览: 125357 次
- 性别:
- 来自: 北京
-
最新评论
-
flforever1213：
裴小星 写道不错。我想分治法在并行计算中应该能够发挥很大的作用 ...
算法 之 分治 - 求解最大值和最小值 -
裴小星：
不错。我想分治法在并行计算中应该能够发挥很大的作用。
算法 之 分治 - 求解最大值和最小值 -
flforever1213：
onewind 写道void heapSort(int* he ...
算法 之 堆 - 排序 -
onewind：
void heapSort(int* heap)中缺少了建堆的 ...
算法 之 堆 - 排序 -
flforever1213：
onewind 写道如何理解，用文字描述下呃，我更新了下文章， ...
SQL 插入带引号的字段
文章列表
之前我们讨论的堆，都把最大键值存储在根节点中，这种类型的堆可以看作是最大堆。
我们还可以创建另一种堆，把最键小值存储在根节点中，根节点以外的节点的键值，大于或等于存储在它父节点中的键值，这种类型的堆可以看作是最小堆。
具体是用最大堆还是最小堆，就根据我们自身的需要来选择了。
堆的算法到这里就讲完了，下面这段代码包括了之前讲过的堆的所有算法：
#include <stdio.h>
#include <stdlib.h>
void siftUp(int* heap, int index);
void siftDown(int* heap, int in ...
给出数组A[1...n]，我们可以将其中的元素用下面的方法以非降序有效地排序。
首先将A变换成堆，并使其具有这样的性质：每个元素的键值是该元素本身，即key(A[i])=A[i],1 ≤ i ≤ n。
转换成堆之后，由于A中各项的最大值存储在A[1]中，可以将A[1]和A[n]交换，使得A[n]是数组中的最大元素。这时A[1]中的元素可能小于存放在它的一个子节点中的元素，于是用过程Sift-down将A[1...n-1]转换成堆。接下来将A[1]和A[n-1]交换，并调整数组A[1...n-2]成为堆。交换元素和调整堆的过程一直重复，直到堆的大小变成1为止，这时，A[1]是最小的。
...
给出一个有n个元素的数组A[1...n]，要创建一个包含这些元素的堆，可以这样进行：从空的堆开始，不断插入每一个元素，直到A完全被转移到堆中为止。因为插入第j个键值用时O(log j)，因此用这种方法创建堆栈的时间复杂性是O(n log n)。
我们知道对应于堆H[1...n]的树的节点可以方便地以自顶向下、从左到右的方式从1到n编码。在这样编码之后，可以用下面的方法，把一棵n个节点的几乎完全的二叉树转换成堆H[1...n]。从最后一个节点开始（编码为n的那一个）到根节点（编码为1的节点），逐个扫描所有的节点，根据需要，每一次将以当前节点为根节点的子树转换成堆。
每一棵只有一片叶子的子 ...
1. 插入
为了把元素x插入到堆H中，先将堆大小加1，然后将x添加到H的末尾，再根据需要，把x上移，直到满足堆特性。
如果n是新堆的大小，那么堆树的高度是⌊log n⌋，所以将一个元素插入大小为n的堆中所需要的时间是O(log n)。 ...
1. Sift-up
假定对于某个i>1，H[i]变成了键值大于它父节点键值的元素，这样就违反了堆的特性。我们需要使用Sift-up运算把新的数据项移到在二叉树中适合它的位置上。
Sift-up的运算沿着从H[i]到根节点的唯一一条路径，把H[i]移到适合它的位置上。在沿着路径的每一步上，都将H[i]键值和它父节点的键值H[⌊i/2⌋]相比较。
过程 Sift-up
输入 数组H[1...n]和位于1和n之间的索引i
输出 上移H[i]（如果需要），以使它不大于父节点
算法描述
done ← false
if i = 1 then exit {节点i为根} ...
在许多算法中，需要支持下面两种元素运算的数据结构：插入元素和寻找最大值元素。支持这两种运算的数据结构称为优先队列。
如果使用普通队列，那么寻找最大元素需要搜索整个队列，开销比较大；如果采用排序数组，那 ...
小弟最近开始了Java的学习之路，希望能够学习一下各种框架。
这两天在接触Struts，网上找了本书Struts in Action(中文版)（惭愧自己的E文水准╮(╯▽╰)╭）。书中的例子是基于Struts1.1的，于是我就用MyEclipse中比较接近的Struts1.3来 ...