加载中…
向堆中插入一个元素的方法
(2007-11-18 21:11:27)
标签：
it/科技 |
题目：整数数组中存贮堆，写一个函数，将一个新的元素插入堆！（大根堆）
思路：向堆中插入一个元素时，首先将该元素写入到堆尾，即堆中最后一个元素的后面，然后经调整为一个新堆。因为在原有堆上插入一个新元素后，可能使以该元素的双亲结点为根的子树不为堆，从而使整个树不为堆，所以必须进行调整使之仍为一个堆。调整的方法如下，若新元素大于双亲结点的值，就让它们互换位置。新元素换到双亲位置后，使得以该位置为根的子树成为堆，但新元素可能还大于此位置的双亲结点的值，从而使以上一层的双亲结点为根的子树不为堆，还需要按上述方法继续调整。这样持续传递上去，直到以新位置的双亲结点为根的子树仍为一个堆或者调整到堆顶为止，此时得到的整个树又成为了一个堆。
源代码：
void siftup(int a[],int *n,int
m)//a[0]是根，*n是元素个数，m是要插入的新元素
{
int i,j,t;
i=*n;
a[i]=m;
(*n)++;
t=a[i];
while((j=(i-1)/2)>=0 && i>0)
{
if(t>a[j])
{
a[i]=a[j];
i=j;
}
else break;
}
a[i]=t;
}
{
}
空间复杂度：O（1），时间复杂度：O（log2n）
喜欢
0
赠金笔
前一篇：求二叉树的高度
后一篇：图的DFS的非递归算法