`
flforever1213
  • 浏览: 124777 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

算法 之 堆 - Sift-up和Sift-down

阅读更多

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为根}

repeat

    if key(H[i]) > key(H[i/2]) then 互换H[i]和H[i/2]

    else done ← true

    i ← i/2

until i = 1 or done

 

注意这里算法描述的数组的索引都是1...n,而不是大家习惯的0...n-1。

// heap[0]用来存储数组中堆数据的长度,堆数据heap[1]...heap[heapLength]
// 所以数组的实际长度是heapLength+1,我们只对从数组索引为1开始的heapLength个数据进行操作
void siftUp(int* heap, int index)
{
	int heapLength = heap[0];

	if (index < 1 || index > heapLength)
		return;

	bool done = false;
	while(!done && index > 1)
	{
		if (heap[index] > heap[index / 2])
		{
			int temp = heap[index];
			heap[index] = heap[index / 2];
			heap[index / 2] = temp;
		}
		else
		{
			done = true;
		}

		index /= 2;
	}
}

 

2. Sift-down

假定对于i ≤ n/2,存储在H[i]中元素的键值变成小于H[2i]和H[2i+1]中的最大值(如果2i+1存在的话),这样也违反了堆的特性。Sift-down运算使H[i]“渗”到二叉树中适合它的位置上,沿着这条路径的每一步,都把H[i]的键值和存储在它子节点(如果存在)中的两个键值里最大的那个相比较。

 

过程  Sift-down

输入  数组H[1...n]和位于1和n之间的索引i

输出  下移H[i](如果需要),以使它不小于子节点

 

算法描述

done ← false

if 2i > n then exit {节点i是叶子}

repeat

    i ← 2i

    if i + 1 ≤ n and key(H[i+1]) > key(H[i]) then i ← i + 1

    if key(H[i/2]) < key(H[i]) then 互换H[i]和H[i/2]

    else done ← true

    end if

until 2i > n or done

 

注意这里算法描述的数组的索引也都是1...n,而不是大家习惯的0...n-1。

// heap[0]用来存储数组中堆数据的长度,堆数据heap[1]...heap[heapLength]
// 所以数组的实际长度是heapLength+1,我们只对从数组索引为1开始的heapLength个数据进行操作
void siftDown(int* heap, int index)
{
	int heapLength = heap[0];

	if (index < 1 || index * 2 > heapLength)
		return;

	bool done = false;
	while(!done && index * 2 <= heapLength)
	{
		index *= 2;

		if (index + 1 <= heapLength && heap[index + 1] > heap[index])
			index += 1;
		
		if (heap[index] > heap[index / 2])
		{
			int temp = heap[index];
			heap[index] = heap[index / 2];
			heap[index / 2] = temp;
		}
		else
		{
			done = true;
		}
	}
}

 

我使用的数组是这样定义的:

const int HEAP_LENGH = 10;
int heap[HEAP_LENGH + 1] = { HEAP_LENGH, 20, 3, 9, 10, 11, 4, 5, 3, 7, 5 };
// 这个数组用 siftDown(heap, 2) 方法可以看到效果

 

更多内容请参考:

算法 之 堆 - 简介

1
2
分享到:
评论
2 楼 flforever1213 2011-03-08  
onewind 写道
恩 heap[0] 保存堆的长度不错,也可以让数组下标从1开始

小弟最近重温算法,多谢支持哈!
1 楼 onewind 2011-03-08  
恩 heap[0] 保存堆的长度不错,也可以让数组下标从1开始

相关推荐

    Sift特征检测算法原理.docx

    SIFT特征检测算法原理.docx SIFT(Scale-invariant feature transform)是一种计算机视觉的算法,用于侦测与描述影像中的局部性特征。该算法由David Lowe于1999年所发表,2004年完善总结。其应用范围包含物体辨识、...

    纯C SIFT算法

    标题中的“纯C SIFT算法”指的是使用...学习和理解这个纯C SIFT算法的实现,不仅有助于掌握SIFT的基本原理,还能深入了解如何用低级语言实现复杂图像处理算法,这对于优化性能和理解计算机视觉的底层机制非常有帮助。

    筛选法调整堆的算法Sift.pdf

    标题中的“筛选法调整堆”(Sift Down)是一种在计算机科学中用于维护堆数据结构的操作,也称为下沉操作或下沉调整。堆是一种特殊的树形数据结构,通常满足堆属性:父节点的值总是大于或等于(在最大堆中)或小于或...

    堆算法 最大堆 最小堆

    堆的构建通常通过上浮(sift-up)或下沉(sift-down)操作完成。上浮过程用于新插入的元素,确保它正确地相对于其父节点定位;下沉过程用于调整因删除根节点而破坏堆性质的情况,使得子节点正确地替换父节点位置。 ...

    算法 堆的创建与堆排序

    这通常涉及到一个名为“下沉”(Sift Down)的操作,即从当前节点开始,比较其与其子节点的值,如果子节点的值更大,则交换它们的位置,重复此过程直到满足最大堆的要求。 #### 三、堆排序 堆排序是一种基于比较的...

    二叉堆(最小堆)+二项堆+斐波那契堆

    同时,为了保持堆的性质,插入和删除操作通常伴随着调整堆的过程,如 sift-up 和 sift-down。 总的来说,二叉堆、二项堆和斐波那契堆是数据结构和算法领域的关键工具,掌握它们的原理和实现对于优化代码性能至关...

    算法与设计堆排序课件

    一旦堆被构建,堆顶元素(最大堆的最大元素或最小堆的最小元素)可以被移除,并通过下沉操作(Sift_down)重新调整堆以保持堆的性质。 堆排序算法的基本步骤如下: 1. **建堆**:将无序序列构造成一个最大堆或最小...

    数据结构 堆的实现

    - 堆的理论基础,包括完全二叉树的概念和堆的性质。 - 使用数组实现堆,理解堆的索引对应关系。 - 实现插入、删除和建堆的算法,分析它们的时间复杂度。 - 应用堆的实际例子,如优先队列、堆排序等。 - 比较不同数据...

    数据结构-3期(KC002) 堆排序算法.docx

    堆排序的基本步骤分为两部分:建立初始堆(Heapify)和调整堆(Sift Down)。首先,我们将待排序的序列构建成一个最大堆,然后将堆顶元素(最大值)与末尾元素交换,将其移出堆并调整剩下的元素使其保持堆的性质,...

    java-二叉堆(堆)binaryHeap

    - 在Java的`PriorityQueue`中,插入元素时,新元素会被放在堆的末尾,并通过上浮(sift-up)操作调整,确保堆的性质得以保持。这个过程涉及比较新元素与其父节点,并根据需要交换位置。 3. **删除操作(Remove)**...

    算法JavaScript实现

    构建大根堆通常通过上滤(sift-up)操作完成,而调整堆则使用下滤(sift-down)。理解堆的性质并熟练运用插入和删除操作是掌握大根堆的关键。 接下来是Canvas棋盘覆盖法。在计算机图形学中,Canvas API允许我们在...

    堆、完全二叉树详解源码

    在实际编程中,这些函数的实现细节可能会根据具体需求有所不同,例如,可以使用递归或迭代方法来实现`sift_up()`和`sift_down()`。同时,源码还会包含错误检查和边界处理等安全措施。 总的来说,理解和掌握堆与完全...

    算法导论第3版

    - **维护堆属性**:讲解了如何保持堆的性质不被破坏,包括向下调整(sift-down)等操作。 #### 四、其他重要知识点 - **第5章:概率分析与随机化算法** - **招聘问题**:通过概率分析来解决问题的一个示例。 - ...

    数组堆操作,包括堆排序、堆插入、堆删除等

    这个过程通常用到两种操作:上滤(sift up)和下滤(sift down)。上滤用于在插入元素后保持堆性质,下滤则用于删除堆顶元素后重新调整堆。 2. 堆插入:在堆中插入新元素时,通常将新元素放在堆的末尾,然后...

    堆排序算法思想,图例讲解算法步骤,另附代码示例

    这个过程称为下沉(sift down)。在完全二叉树中,最后一个非叶子节点的索引是 `(n/2)-1`,其中 `n` 是数组的长度。我们可以使用以下步骤来下沉某个节点: 1. 将父节点的值存入临时变量。 2. 计算左孩子的索引 `...

    算法面试通关40讲完整课件 11-13 优先队列(PriorityQueue)

    对于最小堆,新元素通常被放在最后一个位置,然后通过上滤(sift up)操作将其提升到正确的位置。 - 删除(Extract-Max/Min):删除优先队列的根元素,即最高优先级的元素。在最小堆中,删除最小元素;在最大堆中,...

    Leetcode刷题笔记-堆

    在算法学习和面试准备的过程中,Leetcode是一个不可或缺的资源库。本文将深入探讨堆相关的基础知识及其在Leetcode中的具体应用,特别是针对“Top K”问题的经典解决方案。 #### 堆的基础概念 堆是一种特殊的完全...

    堆创建,删除,排序实现

    初始化堆时,我们可以从最后一个非叶子节点开始,自底向上地执行“上滤”(sift-up)操作,确保每个节点都满足堆性质。对于最大堆,这意味着将父节点与子节点比较并交换,如果必要的话;对于最小堆,操作相同,只是...

    基数排序、堆排序、希尔排序、直接插入排序

    在`堆排序Heap_sort.cpp`中,你可以学习到如何维护堆的性质并进行相应的调整,如 sift-up 和 sift-down 操作,以实现排序。 希尔排序,又称缩小增量排序,是插入排序的一种更高效的改进版本。它通过将待排序的元素...

Global site tag (gtag.js) - Google Analytics