精华内容
下载资源
问答
  • 2022-02-10 13:41:14

    对于给定的最小堆(优先队列),分别实现插入元素和删除堆顶的函数。

    函数接口定义:

    int insertIntoHeap(struct Heap* h, int x);  // 向堆中插入元素x
    int deleteMin(struct Heap* h, int* pElement);  //将堆顶元素拷贝到pElement所指变量并删除堆顶元素
    

    其中,hxpElement为参数,h是堆结构体指针,x是待插入元素的值,pElement指向的变量用于存放删除的堆顶元素。
    堆结构体定义如下:

    struct Heap{
        int *data;  // 堆元素存储空间指针,堆元素从data[1]开始存放,data[0]不使用,无哨兵元素
        int capacity; // 堆容量
        int size; // 堆元素数量
    };
    

    裁判测试程序样例:

    #include <stdio.h>
    #include <stdlib.h>
    struct Heap{
        int *data;
        int capacity;
        int size;
    };
    struct Heap* initHeap(int capacity){   // 初始化堆
        struct Heap* h;
        h = (struct Heap*)malloc(sizeof(struct Heap));
        if(!h) return NULL;
        h->data = (int*)malloc(sizeof(int)*capacity+1);
        if(h->data == NULL){
            free(h);
            return NULL;
        }
        h->capacity = capacity;
        h->size = 0;
        return h;
    };
    void printHeap(struct Heap* h){  // 打印堆元素
        /* 细节省略 */
    }
    int insertIntoHeap(struct Heap* h, int x);
    int deleteMin(struct Heap* h, int* pElement);
    int main(){
        struct Heap *h;
        int n;
        scanf("%d", &n);   // 输入堆容量
        h = initHeap(n);
        int op, x;
        scanf("%d", &op);
        while(op){    // 输入操作: -1表示删除   1表示插入   0表示结束
            if(op == 1){
                scanf("%d", &x);
                printf("Insertion %s. ", insertIntoHeap(h, x) ? "succeeded" : "failed" );
                printHeap(h);
            }
            else{
                if (deleteMin(h, &x) ) printf("%d deleted. ", x);
                else printf("Deletion failed. ");
                printHeap(h);
            }
            scanf("%d", &op);
        }
        return 0;
    }
    
    /*你提交的代码将被嵌在这里 */
    

    输入样例:

    对于样例测试程序规定的输入格式:

    3
    1 10
    1 20
    1 5
    1 40
    -1
    -1
    -1
    -1
    0
    

    输出样例:

    样例测试程序的输出:

    Insertion succeeded. 10, 
    Insertion succeeded. 10, 20, 
    Insertion succeeded. 5, 20, 10, 
    Insertion failed. 5, 20, 10, 
    5 deleted. 10, 20, 
    10 deleted. 20, 
    20 deleted. 
    Deletion failed. 
    int insertIntoHeap(struct Heap* h, int x) {
    	if (h->capacity == h->size)return 0;
    	int i = ++h->size;
    	for (; h->data[i / 2] > x && i > 1; i /= 2)
    		h->data[i] = h->data[i / 2];
    	h->data[i] = x;
    	return 1;
    }
    int deleteMin(struct Heap* h, int* pElement) {
    	if (!h->size)return 0;
    	*pElement = h->data[1];
    	int t = h->data[h->size--];
    	int parent, child;
    	for (parent = 1; parent * 2 <= h->size; parent = child) {
    		child = parent * 2;
    		if (child != h->size && h->data[child] > h->data[child + 1])
    			child++;
    		if (h->data[child] > t)break;
    		else h->data[parent]=h->data[child]
    	}
    	h->data[parent] = t;
    	return 1;
    }

     

    更多相关内容
  • PTA 最小堆插入元素和删除堆顶(无哨兵元素) (20分) 对于给定的最小堆(优先队列),分别实现插入元素和删除堆顶的函数。 函数接口定义: int insertIntoHeap(struct Heap* h, int x); // 向堆中插入元素x int ...

    PTA 最小堆插入元素和删除堆顶(无哨兵元素) (20分)

    对于给定的最小堆(优先队列),分别实现插入元素和删除堆顶的函数。

    函数接口定义:

    int insertIntoHeap(struct Heap* h, int x);  // 向堆中插入元素x
    int deleteMin(struct Heap* h, int* pElement);  //将堆顶元素拷贝到pElement所指变量并删除堆顶元素  
    

    其中,h、x和pElement为参数,h是堆结构体指针,x是待插入元素的值,pElement指向的变量用于存放删除的堆顶元素。

    堆结构体定义如下:

    struct Heap{
        int *data;  // 堆元素存储空间指针,堆元素从data[1]开始存放,data[0]不使用,无哨兵元素
        int capacity; // 堆容量
        int size; // 堆元素数量
    };
    

    裁判测试程序样例:

    #include <stdio.h>
    #include <stdlib.h>
    struct Heap{
        int *data;
        int capacity;
        int size;
    };
    struct Heap* initHeap(int capacity){   // 初始化堆
        struct Heap* h;
        h = (struct Heap*)malloc(sizeof(struct Heap));
        if(!h) return NULL;
        h->data = (int*)malloc(sizeof(int)*capacity+1);
        if(h->data == NULL){
            free(h);
            return NULL;
        }
        h->capacity = capacity;
        h->size = 0;
        return h;
    };
    void printHeap(struct Heap* h){  // 打印堆元素
        /* 细节省略 */
    }
    int insertIntoHeap(struct Heap* h, int x);
    int deleteMin(struct Heap* h, int* pElement);
    int main(){
        struct Heap *h;
        int n;
        scanf("%d", &n);   // 输入堆容量
        h = initHeap(n);
        int op, x;
        scanf("%d", &op);
        while(op){    // 输入操作: -1表示删除   1表示插入   0表示结束
            if(op == 1){
                scanf("%d", &x);
                printf("Insertion %s. ", insertIntoHeap(h, x) ? "succeeded" : "failed" );
                printHeap(h);
            }
            else{
                if (deleteMin(h, &x) ) printf("%d deleted. ", x);
                else printf("Deletion failed. ");
                printHeap(h);
            }
            scanf("%d", &op);
        }
        return 0;
    }
    
    /*你提交的代码将被嵌在这里 */
    

    输入样例:

    对于样例测试程序规定的输入格式:

    3
    1 10
    1 20
    1 5
    1 40
    -1
    -1
    -1
    -1
    0
    

    输出样例:

    样例测试程序的输出:

    Insertion succeeded. 10, 
    Insertion succeeded. 10, 20, 
    Insertion succeeded. 5, 20, 10, 
    Insertion failed. 5, 20, 10, 
    5 deleted. 10, 20, 
    10 deleted. 20, 
    20 deleted. 
    Deletion failed. 
    

    【程序实现】

    int insertIntoHeap(struct Heap* h, int x) {
        if (h->capacity == h->size) return 0;
        int i = ++h->size;
        for(; h->data[i/2] > x && i > 1; i /= 2)
            h->data[i] = h->data[i/2];
        h->data[i] = x;
        return 1;
    }
    int deleteMin(struct Heap* h, int* pElement) {
        if(!h->size) return 0;
        *pElement = h->data[1];
        int t = h->data[h->size--];
        int parent, child;
        for(parent = 1; parent*2 <= h->size; parent = child) {
            child = parent*2;
            if(child != h->size && h->data[child] > h->data[child+1])
                child++;
            if(h->data[child] > t) break;
            else h->data[parent] = h->data[child];
        }
        h->data[parent] = t;
        return 1;
    }
    
    展开全文
  • 6-1 最小堆插入元素和删除堆顶(无哨兵元素) (20分) 对于给定的最小堆(优先队列),分别实现插入元素和删除堆顶的函数。 函数接口定义: int insertIntoHeap(struct Heap* h, int x); // 向堆中插入元素x int ...

    6-1 最小堆插入元素和删除堆顶(无哨兵元素) (20分)
    对于给定的最小堆(优先队列),分别实现插入元素和删除堆顶的函数。

    函数接口定义:
    int insertIntoHeap(struct Heap* h, int x); // 向堆中插入元素x
    int deleteMin(struct Heap* h, int* pElement); //将堆顶元素拷贝到pElement所指变量并删除堆顶元素

    其中,h、x和pElement为参数,h是堆结构体指针,x是待插入元素的值,pElement指向的变量用于存放删除的堆顶元素。
    堆结构体定义如下:

    struct Heap{
        int *data;  // 堆元素存储空间指针,堆元素从data[1]开始存放,data[0]不使用,无哨兵元素
        int capacity; // 堆容量
        int size; // 堆元素数量
    };
    
          
        
    裁判测试程序样例:
    #include <stdio.h>
    #include <stdlib.h>
    struct Heap{
        int *data;
        int capacity;
        int size;
    };
    struct Heap* initHeap(int capacity){   // 初始化堆
        struct Heap* h;
        h = (struct Heap*)malloc(sizeof(struct Heap));
        if(!h) return NULL;
        h->data = (int*)malloc(sizeof(int)*capacity+1);
        if(h->data == NULL){
            free(h);
            return NULL;
        }
        h->capacity = capacity;
        h->size = 0;
        return h;
    };
    void printHeap(struct Heap* h){  // 打印堆元素
        /* 细节省略 */
    }
    int insertIntoHeap(struct Heap* h, int x);
    int deleteMin(struct Heap* h, int* pElement);
    int main(){
        struct Heap *h;
        int n;
        scanf("%d", &n);   // 输入堆容量
        h = initHeap(n);
        int op, x;
        scanf("%d", &op);
        while(op){    // 输入操作: -1表示删除   1表示插入   0表示结束
            if(op == 1){
                scanf("%d", &x);
                printf("Insertion %s. ", insertIntoHeap(h, x) ? "succeeded" : "failed" );
                printHeap(h);
            }
            else{
                if (deleteMin(h, &x) ) printf("%d deleted. ", x);
                else printf("Deletion failed. ");
                printHeap(h);
            }
            scanf("%d", &op);
        }
        return 0;
    }
    

    /*你提交的代码将被嵌在这里 */

    输入样例:
    对于样例测试程序规定的输入格式:

    3
    1 10
    1 20
    1 5
    1 40
    -1
    -1
    -1
    -1
    0
    
          
    

    输出样例:
    样例测试程序的输出:

    Insertion succeeded. 10,
    Insertion succeeded. 10, 20,
    Insertion succeeded. 5, 20, 10,
    Insertion failed. 5, 20, 10,
    5 deleted. 10, 20,
    10 deleted. 20,
    20 deleted.
    Deletion failed.

    int insertIntoHeap(struct Heap* h, int x){
    	if(h->size==h->capacity)
    	return 0;
    	int i;
    	i=++h->size;
    	for(;x<h->data[i/2];i/=2)
    	{
            h->data[i]=h->data[i/2];
            if (i/2 == 0) break;
        }
    	h->data[i]=x;
    	return 1;
    }
    int deleteMin(struct Heap* h, int* pElement){
    	if(h->size==0)
    	return 0;
    	*pElement=h->data[1];
    	int temp=h->data[h->size--];
    	int parent,child;
    	for(parent=1;parent*2<=h->size;parent=child){
    		child=parent*2;
    		if((child!=h->size)&&(h->data[child]>h->data[child+1]))
    		child++;
    		if(temp<=h->data[child])
    		break;
    		else
    		h->data[parent]=h->data[child];
    	}
    	h->data[parent]=temp;
    	return 1;
    }
    
    展开全文
  • 最大堆和最小堆在算法中也有运用。比如用最大堆求N个数中前K个最小的数,用最小堆求N个数中前K个最大的数。你懂了吗????不懂自己搜吧! 开始正文: 前一阵子一直在写排序的系列文章,最近因为一些事情耽搁了几天...

    先说一下最大堆如何排序:转自:http://www.cnblogs.com/luchen927/archive/2012/03/08/2381446.html

    最大堆和最小堆在算法中也有运用。比如用最大堆求N个数中前K个最小的数,用最小堆求N个数中前K个最大的数。你懂了吗????不懂自己搜吧!

    开始正文:

    前一阵子一直在写排序的系列文章,最近因为一些事情耽搁了几天,也穿插了几篇其他类别的随笔。今天还是回到排序上面来,善始善终,呵呵。
    今天要介绍的也是一种效率很高的排序——堆排序
    思想
    堆排序,顾名思义,就是基于堆。因此先来介绍一下堆的概念。
    堆分为最大堆和最小堆,其实就是完全二叉树。最大堆要求节点的元素都要大于其孩子,最小堆要求节点元素都小于其左右孩子,两者对左右孩子的大小关系不做任何要求,其实很好理解。有了上面的定义,我们可以得知,处于最大堆的根节点的元素一定是这个堆中的最大值。其实我们的堆排序算法就是抓住了堆的这一特点,每次都取堆顶的元素,将其放在序列最后面,然后将剩余的元素重新调整为最大堆,依次类推,最终得到排序的序列。
    或者说,堆排序将所有的待排序数据分为两部分,无序区和有序区。无序区也就是前面的最大堆数据,有序区是每次将堆顶元素放到最后排列而成的序列。每一次堆排序过程都是有序区元素个数增加,无序区元素个数减少的过程。当无序区元素个数为1时,堆排序就完成了。
    本质上讲,堆排序是一种选择排序,每次都选择堆中最大的元素进行排序。只不过堆排序选择元素的方法更为先进,时间复杂度更低,效率更高。
    图例说明一下:(图片来自http://www.cnblogs.com/zabery/archive/2011/07/26/2117103.html)


    具体步骤如下:

      1 首先从第一个非叶子节点开始,比较当前节点和其孩子节点,将最大的元素放在当前节点,交换当前节点和最大节点元素。

      2 将当前元素前面所有的元素都进行1的过程,这样就生成了最大堆

      3 将堆顶元素和最后一个元素交换,列表长度减1。由此无序区减1,有序区加1

      4 剩余元素重新调整建堆

      5 继续3和4,直到所有元素都完成排序

    再来描述一下最大堆和最小堆的插入,删除等,转载自http://www.java3z.com/cwbwebhome/article/article1/1362.html?id=4745


    堆有最大堆和最小堆之分,最大堆就是每个节点的值都>=其左右孩子(如果有的话)值的完全二叉树。最小堆便是每个节点的值都<=其左右孩子值的完全二叉树。 

      设有n个元素的序列{k1,k2,...,kn},当且仅当满足下列关系时,称之为堆。 
     

    堆的三种基本操作(以下以最大堆为例): 
    ⑴最大堆的插入   

        由于需要维持完全二叉树的形态,需要先将要插入的结点x放在最底层的最右边,插入后满 足完全二叉树的特点; 
      然后把x依次向上调整到合适位置满足堆的性质,例如下图中插入80,先将80放在最后,然后两次上浮到合适位置. 


      时间:O(logn)。  “结点上浮” 


    程序实现: 

    
     
    1. //向最大堆中插入元素, heap:存放堆元素的数组
    2. public static void insert(List<Integer> heap, int value) {
    3. //在数组的尾部添加
    4. if(heap.size()== 0)
    5. heap.add( 0); //数组下标为0的位置不放元素
    6. heap.add(value);
    7. //开始上升操作
    8. // heapUp2(heap, heap.size() - 1);
    9. heapUp(heap, heap.size() - 1);
    10. }
    11. //上升,让插入的数和父节点的数值比较,当大于父节点的时候就和父节点的值相交换
    12. public static void heapUp(List<Integer> heap, int index) {
    13. //注意由于数值是从下标为1开始,当index = 1的时候,已经是根节点了
    14. if (index > 1) {
    15. //求出父亲的节点
    16. int parent = index / 2;
    17. //获取相应位置的数值
    18. int parentValue = (Integer) heap.get(parent);
    19. int indexValue = (Integer) heap.get(index);
    20. //如果父亲节点比index的数值小,就交换二者的数值
    21. if (parentValue < indexValue) {
    22. //交换数值
    23. swap(heap, parent, index);
    24. //递归调用
    25. heapUp(heap, parent);
    26. }
    27. }
    28. }


    ⑵删除  
       操作原理是:当删除节点的数值时,原来的位置就会出现一个孔,填充这个孔的方法就是, 
    把最后的叶子的值赋给该孔并下调到合适位置,最后把该叶子删除。 
      
    如图中要删除72,先用堆中最后一个元素来35替换72,再将35下沉到合适位置,最后将叶子节点删除。 
       “结点下沉” 


    
     
    1. 程序:
    2. /**
    3. * 删除堆中位置是index处的节点
    4. * 操作原理是:当删除节点的数值时,原来的位置就会出现一个孔
    5. * 填充这个孔的方法就是,把最后的叶子的值赋给该孔,最后把该叶子删除
    6. * @param heap
    7. */
    8. public static void delete(List<Integer> heap,int index) {
    9. //把最后的一个叶子的数值赋值给index位置
    10. heap.set(index, heap.get(heap.size() - 1));
    11. //下沉操作
    12. //heapDown2(heap, index);
    13. heapDown(heap, index);
    14. //把最后一个位置的数字删除
    15. heap.remove(heap.size() - 1);
    16. }
    17. /**
    18. * 递归实现
    19. * 删除堆中一个数据的时候,根据堆的性质,应该把相应的位置下移,才能保持住堆性质不变
    20. * @param heap 保持堆元素的数组
    21. * @param index 被删除的那个节点的位置
    22. */
    23. public static void heapDown(List<Integer> heap, int index) {
    24. //因为第一个位置存储的是空值,不在考虑之内
    25. int n = heap.size() - 2;
    26. //记录最大的那个儿子节点的位置
    27. int child = - 1;
    28. //2*index>n说明该节点没有左右儿子节点了,那么就返回
    29. if ( 2 * index > n) {
    30. return;
    31. } //如果左右儿子都存在
    32. else if ( 2 * index < n) {
    33. //定义左儿子节点
    34. child = 2 * index;
    35. //如果左儿子小于右儿子的数值,取右儿子的下标
    36. if ((Integer) heap.get(child) < (Integer) heap.get(child + 1)) {
    37. child++;
    38. }
    39. } //如果只有一个儿子(左儿子节点)
    40. else if ( 2 * index == n) {
    41. child = 2 * index;
    42. }
    43. if ((Integer) heap.get(child) > (Integer) heap.get(index)) {
    44. //交换堆中的child,和index位置的值
    45. swap(heap, child, index);
    46. //完成交换后递归调用,继续下降
    47. heapDown(heap, child);
    48. }
    49. }


    ⑶初始化 
    方法1:插入法: 
      从空堆开始,依次插入每一个结点,直到所有的结点全部插入到堆为止。 
      时间:O(n*log(n)) 
      方法2:调整法: 
        序列对应一个完全二叉树;从最后一个分支结点(n div 2)开始,到根(1)为止,依次对每个分支结点进行调整(下沉),
    以便形成以每个分支结点为根的堆,当最后对树根结点进行调整后,整个树就变成了一个堆。 
      时间:O(n) 
    对如图的序列,要使其成为堆,我们从最后一个分支结点(10/2),其值为72开始,依次对每个分支节点53,18,36 45进行调整(下沉). 



    
     
    1. 程序:
    2. /*根据树的性质建堆,树节点前一半一定是分支节点,即有孩子的,所以我们从这里开始调整出初始堆*/
    3. public static void adjust(List<Integer> heap){
    4. for ( int i = heap.size() / 2; i > 0; i--)
    5. adjust(heap,i, heap.size()- 1);
    6. System.out.println( "=================================================");
    7. System.out.println( "调整后的初始堆:");
    8. print(heap);
    9. }
    10. /**
    11. * 调整堆,使其满足堆得定义
    12. * @param i
    13. * @param n
    14. */
    15. public static void adjust(List<Integer> heap,int i, int n) {
    16. int child;
    17. for (; i <= n / 2; ) {
    18. child = i * 2;
    19. if(child+ 1<=n&&heap.get(child)<heap.get(child+ 1))
    20. child+= 1; /*使child指向值较大的孩子*/
    21. if(heap.get(i)< heap.get(child)){
    22. swap(heap,i, child);
    23. /*交换后,以child为根的子树不一定满足堆定义,所以从child处开始调整*/
    24. i = child;
    25. } else break;
    26. }
    27. }


    (4)最大堆排序   

    
     
    1. //对一个最大堆heap排序
    2. public static void heapSort(List<Integer> heap) {
    3. for ( int i = heap.size()- 1; i > 0; i--) {
    4. /*把根节点跟最后一个元素交换位置,调整剩下的n-1个节点,即可排好序*/
    5. swap(heap, 1, i);
    6. adjust(heap, 1, i - 1);
    7. }
    8. }


    (5)完整的代码 
    
     
    1. import java.util.*;
    2. /**
    3. *实现的最大堆的插入和删除操作
    4. * @author Arthur
    5. */
    6. public class Heap {
    7. /**
    8. * 删除堆中位置是index处的值
    9. * 操作原理是:当删除节点的数值时,原来的位置就会出现一个孔
    10. * 填充这个孔的方法就是,把最后的叶子的值赋给该孔,最后把该叶子删除
    11. * @param heap 一个最大堆
    12. */
    13. public static void delete(List<Integer> heap,int index) {
    14. //把最后的一个叶子的数值赋值给index位置
    15. heap.set(index, heap.get(heap.size() - 1));
    16. //下沉操作
    17. //heapDown2(heap, index);
    18. heapDown(heap, index); //节点下沉
    19. //把最后一个位置的数字删除
    20. heap.remove(heap.size() - 1);
    21. }
    22. /**
    23. * 节点下沉递归实现
    24. * 删除一个堆中一个数据的时候,根据堆的性质,应该把相应的位置下移,才能保持住堆性质不变
    25. * @param heap 保持最大堆元素的数组
    26. * @param index 被删除的那个节点的位置
    27. */
    28. public static void heapDown(List<Integer> heap, int index) {
    29. //因为第一个位置存储的是空值,不在考虑之内
    30. int n = heap.size() - 2;
    31. //记录最大的那个儿子节点的位置
    32. int child = - 1;
    33. //2*index>n说明该节点没有左右儿子节点了,那么就返回
    34. if ( 2 * index > n) {
    35. return;
    36. } //如果左右儿子都存在
    37. else if ( 2 * index < n) {
    38. //定义左儿子节点
    39. child = 2 * index;
    40. //如果左儿子小于右儿子的数值,取右儿子的下标
    41. if ((Integer) heap.get(child) < (Integer) heap.get(child + 1)) {
    42. child++;
    43. }
    44. } //如果只有一个儿子(左儿子节点)
    45. else if ( 2 * index == n) {
    46. child = 2 * index;
    47. }
    48. if ((Integer) heap.get(child) > (Integer) heap.get(index)) {
    49. //交换堆中的child,和index位置的值
    50. swap(heap, child, index);
    51. //完成交换后递归调用,继续下降
    52. heapDown(heap, child);
    53. }
    54. }
    55. //非递归实现
    56. public static void heapDown2(List<Integer> heap, int index) {
    57. int child = 0; //存储左儿子的位置
    58. int temp = (Integer) heap.get(index);
    59. int n = heap.size() - 2;
    60. //如果有儿子的话
    61. for (; 2 * index <= n; index = child) {
    62. //获取左儿子的位置
    63. child = 2 * index;
    64. //如果只有左儿子
    65. if (child == n) {
    66. child = 2 * index;
    67. } //如果右儿子比左儿子的数值大
    68. else if ((Integer) heap.get(child) < (Integer) heap.get(child + 1)) {
    69. child++;
    70. }
    71. //如果数值最大的儿子比temp的值大
    72. if ((Integer) heap.get(child) >temp) {
    73. //交换堆中的child,和index位置的值
    74. swap(heap, child, index);
    75. } else {
    76. break;
    77. }
    78. }
    79. }
    80. //打印链表
    81. public static void print(List<Integer> list) {
    82. for ( int i = 1; i < list.size(); i++) {
    83. System.out.print(list.get(i) + " ");
    84. }
    85. System.out.println();
    86. }
    87. //把堆中的a,b位置的值互换
    88. public static void swap(List<Integer> heap, int a, int b) {
    89. //临时存储child位置的值
    90. int temp = (Integer) heap.get(a);
    91. //把index的值赋给child的位置
    92. heap.set(a, heap.get(b));
    93. //把原来的child位置的数值赋值给index位置
    94. heap.set(b, temp);
    95. }
    96. //向最大堆中插入元素
    97. public static void insert(List<Integer> heap, int value) {
    98. //在数组的尾部添加要插入的元素
    99. if(heap.size()== 0)
    100. heap.add( 0); //数组下标为0的位置不放元素
    101. heap.add(value);
    102. //开始上升操作
    103. // heapUp2(heap, heap.size() - 1);
    104. heapUp(heap, heap.size() - 1);
    105. }
    106. //节点上浮,让插入的数和父节点的数值比较,当大于父节点的时候就和节点的值相交换
    107. public static void heapUp(List<Integer> heap, int index) {
    108. //注意由于数值是从小标为一开始,当index = 1的时候,已经是根节点了
    109. if (index > 1) {
    110. //保存父亲的节点
    111. int parent = index / 2;
    112. //获取相应位置的数值
    113. int parentValue = (Integer) heap.get(parent);
    114. int indexValue = (Integer) heap.get(index);
    115. //如果父亲节点比index的数值小,就交换二者的数值
    116. if (parentValue < indexValue) {
    117. //交换数值
    118. swap(heap, parent, index);
    119. //递归调用
    120. heapUp(heap, parent);
    121. }
    122. }
    123. }
    124. //非递归实现
    125. public static void heapUp2(List<Integer> heap, int index) {
    126. int parent = 0;
    127. for (; index > 1; index /= 2) {
    128. //获取index的父节点的下标
    129. parent = index / 2;
    130. //获得父节点的值
    131. int parentValue = (Integer) heap.get(parent);
    132. //获得index位置的值
    133. int indexValue = (Integer) heap.get(index);
    134. //如果小于就交换
    135. if (parentValue < indexValue) {
    136. swap(heap, parent, index);
    137. }
    138. }
    139. }
    140. /*根据树的性质建堆,树节点前一半一定是分支节点,即有孩子的,所以我们从这里开始调整出初始堆*/
    141. public static void adjust(List<Integer> heap){
    142. for ( int i = heap.size() / 2; i > 0; i--)
    143. adjust(heap,i, heap.size()- 1);
    144. System.out.println( "=================================================");
    145. System.out.println( "调整后的初始堆:");
    146. print(heap);
    147. }
    148. /**
    149. * 调整堆,使其满足堆得定义
    150. * @param i
    151. * @param n
    152. */
    153. public static void adjust(List<Integer> heap,int i, int n) {
    154. int child;
    155. for (; i <= n / 2; ) {
    156. child = i * 2;
    157. if(child+ 1<=n&&heap.get(child)<heap.get(child+ 1))
    158. child+= 1; /*使child指向值较大的孩子*/
    159. if(heap.get(i)< heap.get(child)){
    160. swap(heap,i, child);
    161. /*交换后,以child为根的子树不一定满足堆定义,所以从child处开始调整*/
    162. i = child;
    163. } else break;
    164. }
    165. }
    166. //对一个最大堆heap排序
    167. public static void heapSort(List<Integer> heap) {
    168. for ( int i = heap.size()- 1; i > 0; i--) {
    169. /*把根节点跟最后一个元素交换位置,调整剩下的n-1个节点,即可排好序*/
    170. swap(heap, 1, i);
    171. adjust(heap, 1, i - 1);
    172. }
    173. }
    174. public static void main(String args[]) {
    175. List<Integer> array = new ArrayList<Integer>(Arrays.asList( null,
    176. 1, 2, 5, 10, 3, 7, 11, 15, 17, 20, 9, 15, 8, 16));
    177. adjust(array); //调整使array成为最大堆
    178. delete(array, 8); //堆中删除下标是8的元素
    179. System.out.println( "删除后");
    180. print(array);
    181. insert(array, 99); //堆中插入
    182. print(array);
    183. heapSort(array); //排序
    184. System.out.println( "将堆排序后:");
    185. print(array);
    186. System.out.println( "-------------------------");
    187. List<Integer> array1= new ArrayList<Integer>();
    188. insert(array1, 0);
    189. insert(array1, 1);insert(array1, 2);insert(array1, 5);
    190. insert(array1, 10);insert(array1, 3);insert(array1, 7);
    191. insert(array1, 11);insert(array1, 15); insert(array1, 17);
    192. insert(array1, 20);insert(array1, 9);
    193. insert(array1, 15);insert(array1, 8);insert(array1, 16);
    194. print(array1);
    195. System.out.println( "==============================");
    196. array= new ArrayList<Integer>(Arrays.asList( null, 45, 36, 18, 53, 72, 30, 48, 93, 15, 35));
    197. adjust(array);
    198. insert(array, 80); //堆中插入
    199. print(array);
    200. delete(array, 2); //堆中删除80的元素
    201. print(array);
    202. delete(array, 2); //堆中删除72的元素
    203. print(array);
    204. }
    205. }


    程序运行: 
    D:\java>java   Heap 
    ================================================= 
    调整后的初始堆: 
    20 17 16 15 9 15 11 1 10 3 2 7 8 5 
    删除后 
    20 17 16 15 9 15 11 5 10 3 2 7 8 
    99 17 20 15 9 15 16 5 10 3 2 7 8 11 
    将堆排序后: 
    2 3 5 7 8 9 10 11 15 15 16 17 20 99 
    ------------------------- 
    20 17 16 10 15 9 15 0 5 2 11 1 7 3 8 
    ============================== 
    ================================================= 
    调整后的初始堆: 
    93 72 48 53 45 30 18 36 15 35 
    93 80 48 53 72 30 18 36 15 35 45 
    93 72 48 53 45 30 18 36 15 35 
    93 53 48 36 45 30 18 35 15 


    展开全文
  • 对于给定的最小堆(优先队列),分别实现插入元素和删除堆顶的函数。 函数接口定义: int insertIntoHeap(struct Heap* h, int x); // 向堆中插入元素x int deleteMin(struct Heap* h, int* pElement); //将堆顶元素...
  • 堆---实现最小堆及堆的插入与删除

    万次阅读 2018-07-07 23:52:10
    在优先级队列的各种实现中,是最高效的一种数据结构 假定在各个数据记录(或元素)中存在一个能够标识数据记录(或元素)的数据项,并将依据该数据项对数据进行组织,则可数据项成为关键码(key) 如果有...
  • 最小堆两个基本功能实现
  • 最小堆,是一种经过排序的完全二叉树,其中任一非终端节点的数据值均不大于其左子节点和右子节点的值。 通俗的说就是: 1.数组来实现二叉树,所以满足二叉树的特性。 2.根元素是最小的元素,父节点小于它的两个子节点...
  • 最小堆的构建、插入、删除的过程。搞懂最小堆的相应知识后,最大堆与此类似。 2.最小堆示例 3.最小堆的构建 初始数组为:9,3,7,6,5,1,10,2 按照完全二叉树,将数字依次填入。 填入后,找到最后一个结点...
  • c++ 最小堆实现

    2011-11-27 15:25:48
    c++ 最小堆 还不错 标准库没有 自己做作业用。
  • 最大最小堆插入与删除

    千次阅读 2015-07-20 11:05:05
    最大堆、最小堆是一种用可用数组存储,并模拟实现二叉树的数据结构。 最大(小)堆具有以下的显著性质: ●最大(小)堆是一棵树,且是完全二叉树。 ●最大(小)堆是每个根节点都一定大(小)于等于其子节点。 ...
  • 堆是一种经过排序的完全二叉树,其中任一非终端节点...而最大-最小堆集结了最大堆和最小堆的优点,这也是其名字的由来。 最大-最小堆是最大层和最小层交替出现的二叉树,即最大层结点的儿子属于最小层,最小层结点的儿
  • 最详细的最小堆构建、插入、删除的过程图解

    万次阅读 多人点赞 2016-09-30 17:22:09
    1.简介 ... 最小堆是一棵完全二叉树,非叶子结点的值不大于左孩子和右孩子的值...最小堆的构建、插入、删除的过程。搞懂最小堆的相应知识后,最大堆与此类似。 2.最小堆示例 3.最小堆的构建  
  • 堆是一种特殊的“队列”,它取出元素的顺序是依照元素的优先级大小,而不是元素进入...根据最小堆的结构特性,本文使用含有哨兵元素的数组实现了最小堆的创建、插入和删除。 数据类型定义和函数声明 #include #
  • 创建的方式有两种,一种是一边插入结点,一边调用插入方法调整,这样的时间复杂度就是 O(NlogN),而第二种方式就把时间复杂度缩减到了O(N),它是采用先把结点插入好了,然后再来调整,并不是一边插入一边...
  • 基本概念: ...(英语:heap)是计算机科学中一类特殊的数据结构的统称。通常是一个可以被看做一棵树的数组对象。总是满足下列性质: 中某个节点的值总是不大于或不小于其父节点的值; ...
  • 链接1:https://blog.csdn.net/Genios/article/details/8157031 链接2:https://blog.csdn.net/hrn1216/article/details/51465270
  • 堆数的定义 堆树的定义如下: (1)堆树是一颗完全二叉树; (2)堆树中某个节点的值总是不大于或不小于其孩子节点的值; (3)堆树中每个节点的子树都...建立最大堆和最小堆的过程,就是对原有的数组中不断交换父亲...
  • 本人编写的排序及插入删除等操作演示,用的是java swing,详情可以查看 http://blog.csdn.net/cdnight/article/details/11714005 假如您对排序不是很熟悉,可以查看 ...
  • 1.简介  最小堆是一棵完全二叉树,非叶子结点的值不大于左孩子和右孩子...最小堆的构建、插入、删除的过程。搞懂最小堆的相应知识后,最大堆与此类似。 2.最小堆示例 3.最小堆的构建  初始数组为
  • 显然,最小堆对于插入、更新和删除有一个大 O(log n),所以它比有一个大 O(1) 的 OrderedDict 慢得多。 也就是说,在达到缓存容量之前,最小堆实际上会稍微快一点。 对具有 5 000 000 个元素容量的 3 个不同缓存...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 109,411
精华内容 43,764
关键字:

最小堆的插入

友情链接: gen-tn74.zip