赞
踩
堆是一类特殊的树,堆的通用特点就是父节点会大于或小于所有子节点(儿子不分左右)。一个最小堆(min-heap)就是其中的每一个节点都小于或等于其两个子节点的一个二叉树。一个最大堆(max-heap)将最大的节点放置到最靠近根节点的位置。
注意:不能把这种类型的堆和计算机用于管理动态内存的堆搞混了。下面是区别:
数据结构中:栈是一种具有后进先出的数据结构,堆是一种经过排序的树形数据结构,每个节点都有一个值。通常我们所说的堆的数据结构是指二叉树。堆的特点是根节点的值最小(或最大),且根节点的两个树也是一个堆。由于堆的这个特性,常用来实现优先队列。
内存分配中:栈是系统自动分配空间的,堆则是程序员根据需要自己申请的空间。由于栈上的空间是自动分配自动回收的,所以栈上的数据的生存周期只是在函数的运行过程中,运行后就释放掉,不可以再访问。而堆上的数据只要程序员不释放空间,就一直可以访问到,不过缺点是一旦忘记释放会造成内存泄露。使用栈就像我们去饭馆里吃饭,只管点菜(发出申请)、付钱、吃(使用),吃饱了就走,不必理会切菜,洗菜等准备工作和洗碗、刷锅等扫尾工作,他的好处就是快捷,但是自由度小。使用堆就像是自己动手做喜欢的菜肴,比较麻烦,但是比较符合自己的口味,而且自由度大。
我们将使用堆来实现一个优先队列,堆接口应该包含返回其大小、添加项、删除项和查看项的方法。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。