精华内容
下载资源
问答
  • 链接1:https://blog.csdn.net/Genios/article/details/8157031 链接2:https://blog.csdn.net/hrn1216/article/details/51465270
    展开全文
  • 最小堆,是一种经过排序的完全二叉树,其中任一非终端节点的数据值均不大于其左子节点和右子节点的值。 通俗的说就是: 1.数组来实现二叉树,所以满足二叉树的特性。 2.根元素是最小的元素,父节点小于它的两个子节点...

    最小堆,是一种经过排序的完全二叉树,其中任一非终端节点的数据值均不大于其左子节点和右子节点的值。
    通俗的说就是:
    1.数组来实现二叉树,所以满足二叉树的特性。
    2.根元素是最小的元素,父节点小于它的两个子节点。
    3.树中的元素是相对有序的。

    如何实现堆的相对有序是关键。

    插入元素时,插入到数组中的最后一个元素的后面,然后与该节点的父节点比较大小。如果插入的元素小于父节点元素,那么与父节点交换位置。然后插入元素交换到父节点位置时,又与该节点的父节点比较,直到大于父节点元素或者到达堆顶。该过程叫做上浮,即插入时上浮。

    移除元素时,只能从堆顶移除元素,再取最后一个元素放到堆顶中。然后堆顶节点与子节点比较时,先取子节点中的较小者,如果堆顶节点大于较小子节点,那么交换位置。此时堆顶节点元素交换到较小子节点上。然后再与其较小子节点比较,直到小于较小子节点或者到达叶子节点为止。该过程叫做下沉,即移除元素时下沉。

    附上一个简单的最小堆插入代码:

    #include <stdio.h>
    #define MAXN 1005
    #define MINDATA -10005
    int Data[MAXN], size;
    void Insert(int x) {
        int i = ++size;
        for( ; x < Data[i/2]; i /= 2)
            Data[i] = Data[i/2];
        Data[i] = x;
    }
    int main() {
        int N, M;
        int x;
        scanf("%d%d", &N, &M);
        Data[0] = MINDATA;
        size = 0;
        while(N--) {
            scanf("%d", &x);
            Insert(x);
        }
        while(M--) {
            scanf("%d", &x);
            printf("%d", Data[x]);//指定节点到根节点的路径遍历
            x /= 2;
            while(x) {
                printf(" %d", Data[x]);
                x /= 2;
            }
            printf("\n");
        }
        return 0;
    }
    
    
    展开全文
  • 2.序性:任一结点的关键字是其子树所有结点的最大值(最大)或最小值(最小堆),即任意子树也应该是个。 根据最小堆的结构特性,本文使用含有哨兵元素的数组实现了最小堆的创建、插入和删除。 数据类型...

    堆是一种特殊的“队列”,它取出元素的顺序是依照元素的优先级大小,而不是元素进入队列的先后顺序。堆具有两个特性,1.结构性:它是能用数组表示的完全二叉树。2.堆序性:任一结点的关键字是其子树所有结点的最大值(最大堆)或最小值(最小堆),即任意子树也应该是个堆。

    根据最小堆的结构特性,本文使用含有哨兵元素的数组实现了最小堆的创建、插入和删除。

    数据类型定义和函数声明

    #include<stdio.h>
    #include<stdlib.h>
    
    #define MinData -100//哨兵元素的值
    typedef struct HeapStruct{
    	int *p;
    	int size;
    	int capacity;
    } *MinHeap;
    
    MinHeap Init_MinHeap(int MaxSize);
    int IsFull(MinHeap H);
    int IsEmpty(MinHeap H);
    void Insert(MinHeap H, int data);
    int Delete(MinHeap H);
    void BuildMinHeap(MinHeap H, int N);
    void PrintValue(MinHeap H);
    

    程序中用到的功能函数

    int IsFull(MinHeap H)
    {
    	return (H->size == H->capacity) ? 1 : 0;
    }
    
    int IsEmpty(MinHeap H)
    {
    	return (H->size == 0) ? 1 : 0;
    }
    
    void PrintValue(MinHeap H)
    {
    	int i;
    	printf("最小堆中的元素依次为:");
    	for (i = 1; i <= H->size; i++)
    		printf("%d ", H->p[i]);
    	printf("\n");
    }

    最小堆的初始化

    该函数给最小堆分配了内存空间并完成初始化操作,此时最小堆中元素为空。

    MinHeap Init_MinHeap(int MaxSize)
    {
    	MinHeap H = (MinHeap)malloc(sizeof(HeapStruct));
    	H->p = (int*)malloc((MaxSize + 1) * sizeof(int));
    	H->p[0] = MinData;
    	H->size = 0;
    	H->capacity = MaxSize;
    	return H;
    }

    在最小堆中插入元素

    插入元素的关键是把要插入的元素放在最小堆的合适位置中。所谓合适即不破坏最小堆的结构性和堆序性。

    为了将一个元素data插入到堆中,在遵守堆的结构性特点(完全二叉树)基础上,在下一个空闲位置创建一个空穴。如果元素data可以放在该空穴中而并不破坏堆的序,则完成插入。否则,把空穴的父节点上的元素移入该空穴中,这样,空穴就朝着根的方向上移动一层。继续该过程知道元素data能放入空穴中。因为空穴在逐渐往树的上方移动,所以把这种策略成为“上滤”。

    void Insert(MinHeap H, int data)
    {
    	int i;
    	if (IsFull(H))
    	{
    		printf("最小堆已满,无法插入元素");
    		return;
    	}
    	for (i = ++H->size; data < H->p[i / 2]; i /= 2)
    		H->p[i] = H->p[i / 2];
    	H->p[i] = data;
    }

    删除最小堆中的最小元素

    删除元素的关键是把堆中最后一个元素移动到最小堆中的合适位置。所谓合适即不破坏最小堆的结构性和堆序性。

    删除元素以类似于插入的方式处理。找到最小元很容易(第一个元素),困难的部分是删除后的调整。当删除一个最小元时,在根节点处产生一个空穴。由于现在堆里少了一个元素,因为堆中最后一个元素lastvalue必须移动到该堆的某个地方。通常我们将空穴的两个儿子中较小者移入空穴,这样就把空穴向下退了一层。重复该步骤知道lastvalue可以放在空穴中。通常把这种策略成为“下滤”。

    int Delete(MinHeap H)
    {
    	int minvalue , lastvalue, child, parent;
    	if (IsEmpty(H))
    	{
    		printf("最小堆已满,无法删除元素");
    		return -999;
    	}
    
    	minvalue = H->p[1];
    	lastvalue = H->p[H->size--];
    	for (parent = 1; 2 * parent <= H->size; parent = child)
    	{
    		child = 2 * parent;/*默认左结点的元素值更小*/
    		if (child != H->size && H->p[child + 1] < H->p[child])/*若右节点的元素值更小,则调整child*/
    			child++;
    		if (lastvalue < H->p[child])
    			break;
    		else
    			H->p[parent] = H->p[child];
    	}
    	H->p[parent] = lastvalue;
    	return minvalue;
    }

    创建最小堆

    在创建最小堆时,可以 : 通过插入操作Insert函数,将N 个元素一个个相继插入到一个初始为空的堆中去 ,但其时间代价最大为O(NlogN)。

    也可以在线性复杂度下建立最小堆,基本步骤为:1. 将N个元素按输入顺序存入,先满足完全二叉树的结构特性。2.调整各节点位置,以满足最大堆的堆序性。这样创建最小堆时的时间代价为O(N)。在调整节点位置时,只需对从第N/2个节点到第一个节点依次应用“下滤”策略即可,其实也就是进行了N/2次的近似删除操作。

    void BuildMinHeap(MinHeap H, int N)
    {
    	int i, num, parent, child, root, lastvalue;
    	if (N > H->capacity)
    	{
    		printf("要创建的元素个数超过堆的最大容量,创建失败");
    		return;
    	}
    	for (i = 1; i <= N; i++)
    	{
    		printf("请输入要插入的元素值:");
    		scanf_s("%d", &num);
    		H->p[i] = num;
    	}
    	H->size = N;
    
    	root = N / 2;/*从第N/2个结点到第1个结点依次进行下滤 近似N/2次删除操作*/
    	while (root)
    	{
    		lastvalue = H->p[root];
    		for (parent = root; 2 * parent <= H->size; parent = child)
    		{
    			child = 2 * parent;/*默认左结点的元素值更小*/
    			if (child != H->size && H->p[child + 1] < H->p[child])/*右结点元素值更小*/
    				child++;
    			if (lastvalue < H->p[child])
    				break;
    			else
    				H->p[parent] = H->p[child];
    		}
    		H->p[parent] = lastvalue;
    		--root;
    	}
    }
    

    主程序

    测试序列:150 80 40 30 10 70 110 100 20 90 60 50 120 140 130

    正确结果为:10 20 40 30 60 50 110 100 150 90 80 70 120 140 130

    void main()
    {
    	int num;
    	MinHeap H;
    	H = Init_MinHeap(100);
    	BuildMinHeap(H, 15);
    	PrintValue(H);
    
    	printf("请输入你要插入的数据:");
    	scanf_s("%d", &num);
    	Insert(H, num);
    	PrintValue(H);
    	printf("请输入你要插入的数据:");
    	scanf_s("%d", &num);
    	Insert(H, num);
    	PrintValue(H);
    
    	num = Delete(H);
    	printf("删除的元素为:%d\n", num);
    	PrintValue(H);
    }


    展开全文
  • 小根插入和排序

    2017-12-09 11:33:47
    #include #include using namespace std; int hp[105],n,siz; void push(int x)//输(插)入 ...//将最小的置于末尾 siz--; del(); } for(int i=1;i;i++)//从大到小 cout[i] ; return 0; }  
    #include<cstdio>
    #include<iostream>
    using namespace std;
    int hp[105],n,siz;
    void push(int x)//输(插)入 
    {
    	if(hp[x]>=hp[x/2])
    		return;
    	else
    	{
    		int a=hp[x];
    		hp[x]=hp[x/2];
    		hp[x/2]=a;
    		push(x/2);
    	}
    }
    void del()//删除堆顶 维护堆 
    {
    	int now=1;
    	while(2*now<=siz)//有儿子 
    	{
    		int lison=2*now;
    		if(lison<siz && hp[lison+1]<hp[lison])//有右儿子 且 左儿子>右儿子 
    			lison++;
    		if(hp[now]>hp[lison])
    			swap(hp[now],hp[lison]);
    		else break;
    		now=lison;
    	}
    } 
    int main()
    {
    	cin>>n;
    	for(int i=1;i<=n;i++)
    	{
    		cin>>hp[i];
    		push(i);
    	}
    	for(siz=n;siz>=2; )//堆排 
    	{
    		swap(hp[1],hp[siz]);//将最小的置于末尾 
    		siz--; 
    		del();
    	}
    	for(int i=1;i<=n;i++)//从大到小 
    		cout<< hp[i] <<" ";
    	return 0;
    }

     

    展开全文
  • 上次用Java实现了最大的封装,这次就来写一下最小堆的实现吧插入函数的思路: 向插入元素有两种情况,一种是为空,那么就让插入值作为根节点即可;另一种是不为空,那么此时就要进行判断当前节点与其父...
  • 最小堆实现最小优先队列

    千次阅读 2018-09-12 12:48:20
    最小优先队列的可以实现的操作: insert,插入一个元素 min,找到最小的元素 ...实现他的操作是依赖于的操作,比如要插入一个key,实际上就是在中去找key的位置,然后维护。所以要时刻清醒的是现在...
  • 小根的性质:是完全二叉树,根节点的关键字小于等于两个子节点的关键字插入和删除操作都应当保证小根的性质不变。 由于小根是完全二叉树,所以使用数组存放具有显著优势:按照层次遍历将具有n个元素的小根...
  • [数据结构]大根小根堆插入操作

    千次阅读 2018-04-23 22:42:25
    将根节点最大的叫做最大或大根,根节点最小叫做最小堆或小根。常见的有二叉、斐波那契等。以下是C/C++大根小根具体插入方法。后序会深入解析结构。大根堆插入操作:void HeapAdju...
  • 最小堆

    2015-10-19 11:51:07
    最小堆:是指根节点的关键字值是中的最小关键字值,且每个节点若有儿子节点,其关键字值都不大于其儿子节点的关键字最小堆插入操作  步骤: 把待增加的节点编号 i 设置为已知的总节点数加 1 ...
  • 千次阅读 多人点赞 2020-10-20 11:11:19
    如何操作(建立、插入、删除、查找)? when 什么是是特殊的“队列”,从中取出元素是按照元素优先级大小,而不是元素进入队列的先后顺序。 是一颗完全二叉树,其结点的值大于或小于其子结点...
  • import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;...//排序 大根 public class HeapApp { public static void main(String[] args) throws IOEx
  • 插入结果:保证插入一个关键字不在原来树中的节点后,仍为平衡排序二叉树。 前提说明:这里对插入后仍是排序二叉树的操作不做说明。 假如插入新节点后,仍是一棵排序二叉树, 但不是平衡二叉树时:为使得插入后仍...
  • 此坑待埋。 点击打开漫谈经典排序算法:一、从简单选择排序到排序的深度解析链接 ...白话经典算法系列之七 排序 ...二叉排序树与二叉 ...排序(注:这篇文章说明了如何从...最大插入/删除/调整/排序操作...
  • 最小堆:父节点的值不大于子节点。 左右子节点:没有大小的顺序。 的存储: 一般都用数组来存储。下标为i的节点的父节点的下标为(i–1)/2。根节点的左右子节点下标分别为 2∗i+1 和 2∗i+2。例如:下标为0的...
  • 最小堆最大的详细解读

    万次阅读 多人点赞 2016-04-03 16:17:45
    2013-09-13 16:36 16408人阅读 评论(1) ...排序解释第一篇描述不太清楚最大插入删除调整排序操作图解程序JAVA 此坑待埋。 点击打开漫谈经典排序算法:一、从简单选择排序到排序的深度解析链接
  • 下标从1开始,在含有n个关键字的小根(顶元素最小)中,关键字最大的记录有可能存储在()位置上 首先要明白:中括号取整,就是不大于这个数的最大整数 第二要看清下标是从1开始的。那么 1 2 3 4 5 6 7 …n n不论是左...
  • 最小堆的java实现

    千次阅读 2014-08-04 10:40:06
    * 结点 * 节点数据类型为:int */ private int iDate; public Node(int iDate) { super(); this.iDate = iDate; } public int getiDate() { return iDate; } public void seti
  • 最小堆:是指根节点的关键字值是中的最小关键字值,且每个节点若有儿子节点,其关键字值都不大于其儿子节点的关键字值。 最大插入操作 步骤: 1 把待增加的节点编号 i 设置为已知的总节点数加 1 即 i=++(*n)...
  • 优先队列及最小堆最大

    万次阅读 多人点赞 2013-08-25 15:03:03
    n个关键字序列Kl,K2,…,Kn称为(Heap),当且仅当该序列满足如下性质(简称为性质): (1)ki=号。//k(i)相当于二叉树的非叶结点,K(2i)则是左孩子,k(2i+1)是右孩子 若将此序列所存储的向量R[1..n]看做是一...
  • 什么是最大最小堆?最大(小)是指在树中,存在一个结点而且该结点有儿子结点,该结点的data域值都不小于(大于)其儿子结点的data域值,并且它是一个完全二叉树(不是满二叉树)。注意区分选择树,因为选择树...
  • 插入与删除,上浮与下沉

    千次阅读 2017-07-12 22:04:00
    在最大构造,排序,和最大维护的基础上,补充了插入和删除,和其中用到的上浮,下沉等操作。 个人理解:最大维护是用元素A替换掉中某元素后通过最大维护操作使得该依然是最大. 而插入则是插入元素A后...
  • MySQL 面试题

    万次阅读 多人点赞 2019-09-02 16:03:33
    关键字后的列。 2、索引列的基数越大,索引效果越好。 具体为什么,可以看看如下两篇文章: 《MySQL 索引基数》 理解相对简单 《低基数索引为什么会对性能产生负面影响》 写的更原理,所以较为...
  • #include #include ...typedef struct fib_heap_node{//斐波那契结点 int key;//结点值 int degree;//结点度 fib_heap_node *parent;//结点的父结点 fib_heap_node *left;//结点的左兄弟,循环双链表
  • 最大最小堆C++实现

    千次阅读 2016-06-23 21:45:23
    最近学习了最大最小堆数据结构,这个并不难懂,但在编程、编写学习笔记时,发现有不少错误、理解不深刻,有比较多的细节需要注意的,特别是孩子节点的访问条件、几个节点之间的比较出了不少错误,但经过一番努力...
  • 最小堆:是指根节点的关键字值是中的最小关键字值,且每个节点若有儿子节点,其关键字值都不大于其儿子节点的关键字值。 以下的操作以最大为例,最小堆相似。 最大插入操作 步骤: 1、把当前节点数i设置...
  • B-树/B+树/B*树详解(查找+插入

    千次阅读 2016-08-01 10:57:15
    树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 95,365
精华内容 38,146
关键字:

最小堆插入关键字