关键词：

20172328 2018-2019《Java软件结构与数据结构》第八周学习总结

概述 Generalization

教材学习内容总结 A summary of textbook

• 堆(heap)就是具有两个附加属性的一颗二叉树:
  • 第一点：它是一颗完全二叉树 ，即叶子节点都在最后一层靠左侧。
  • 第二点：对每一结点，它小于(大于)或等于其左孩子和右孩子。
• 第二点中满足大于的条件下形成的是一个最大堆（大顶堆），反之则为最小堆（小顶堆）。
• 最小堆将其最小元素存储在该二叉树的根处，且其跟的两个孩子同样还是最小堆。

• 堆中的操作：
  

• addElement操作：

  • addElement方法将给定的Comparable元素添加到堆的恰当位置处，且维持该堆的完全性属性和有序属性。

    • Little Tip：完全树你还记得吗？完全二叉树就是所有叶子都位于h或者h-1层，其中h为log2（n），且n为树中的元素数目，h层的所有叶子都位于该树的左边，那么该树被认为是完全的。

  • 堆就是一棵完全的二叉树，所以对于插入的新结点只存在一个正确的位置。要么是h层左边的下一个空位置，要么是h+1层左边的第一个位置（如果h层为满的话）。
  • 将新结点定位到正确的位置后，我们就必须对这个堆进行排序来保持其有序属性。方法就是对树中的最末一片叶子进行跟踪记录，在一个addElement方法后，最末结点就被设定为插入结点。也就是通过上溯树来保证树的有序性.
• removeMin操作：
  • removeMin方法将删除最小堆中的最小元素并返回它，由于最小元素是存储在最小堆的根处，所以我们需要返回储存在根处的元素并用堆中的另一元素替换它。
  • 要维持该树的完全性，就是把储存在树中最末一片叶子上的元素用来替换根元素。
  • 将存储在最末一片叶子上的元素移动到根处，就必须对该堆进行重新排序来维持该堆的排序属性。
  • 要维持该堆的排序属性，就要从根结点下溯树。具体过程是将该新根元素与其较小的孩子进行比较，且如果孩子更小就将它们互换，沿着树向下继续这一过程，直至该元素要么位于某一叶子中，要么比它的两个孩子都小。
• findMin操作：
  • findMin将返回一个指向最小堆中最小元素的引用，由于最小堆的最小元素就在根处，所以直接返回存储在根处的元素即可。
• 使用堆——堆排序heapSort：
  • 堆排序是对简单选择排序的一种改进。
  • 改进着眼点：如何减少关键字的比较次数
    • 简单选择排序在一趟排序中仅选出最小关键字，但是没有把一趟比较结果保存下来，因而比较次数较多。
    • 堆排序在选出最小关键字同时，也找出较小的关键字，从而减少了后面选择中的比较次数，提高了整个排序效率。
• 左右子树都是大顶堆，如何调整根结点，使得整棵树成为一个堆？
  
• 堆调整 —— 筛选过程
  • 调整过程中，总是将根结点（被调整结点）与左右孩子比较；
  • 不满足堆条件时，将根结点与左右孩子中较大者交换；
  • 这个调整过程一直进行到所有子树都是堆或者交换到叶子为止。
  • 这个从堆顶到叶子的调整过程称为“筛选”。
• 对堆进行筛选完毕之后我们就要为保持其有序性而开始排序。
• 堆排序-排序过程
  
  
  
  • 从无序序列的第[n/2]个元素开始（对应于完全二叉树的最后一个非终端结点）进行筛选；
  • 当解决一个非终端结点（非叶子结点）的有序问题后，把此非终端结点看做一个叶子，然后继续上溯，找到倒数第二个非终端结点，继续进行有序替换，知道整个堆有序为止。
• heapSort的复杂度为O（nlogn）
• 使用堆：优先级队列
• 优先级队列（Priority queue）就是遵循两个排序规则的集合。
  • 首先，具有更高优先级的项目在先。

  • 其次，具有相同优先级的项目使用先进先出方法来确定其排序。

    • Little Tip:虽然最小堆根本就不是一个队列，但是它却提供了一个高效的优先级队列实现。

• 用链表实现堆：
  • 因为我们要求在插入元素后能够向上遍历该树，所以堆中的结点必须存储在指向其双亲的指针。所以我们从创建一个HeapNode类开始我们的链表实现，该类对BinaryTreeNode进行了拓展并添加了一个双亲指针。
  • 链表实现的实例数据由指向HeapNode且称为lastNode的单个引用组成，这样我们就能够跟踪记录该堆中最末一片叶子。public HeapNode lastNode;
  • addElement操作：
    • 在恰当的位置添加一个新元素
    • 对堆进行重排序以维持其排序属性
    • 将lastNode指针重新设定指向新的最末结点
  • removeMin操作：
    • 用存储在最末结点处的元素替换存储在根处的元素
    • 对堆进行重排序
    • 返回原始的根元素
  • findMin操作：
    • 该方法仅仅返回一个指向存储在堆根处元素的引用，因此复杂度为O（1）。
• 用数组实现堆：
  • 用数组实现堆不再需要创建一个HeapNode类对，而是通过用数组来保存堆中的数据。
  • 在二叉树的数组实现中，树的根位于位置0处，对于每一结点n，n的左孩子将位于数组的2n+1处，右孩子将位于数组的2n+2处。
  • addElement操作：
    • 在恰当的位置添加一个新元素
    • 对堆进行重排序以维持其排序属性
    • 将count递增1.
  • removeMin操作：
    • 用存储在最末结点处的元素替换存储在根处的元素
    • 对堆进行重排序
    • 返回原始的根元素
  • findMin操作：
    • 返回指向存储在堆的根处或数组0位置处的元素。

• 总结：链表实现和数组实现的addElement方法和removeElement方法时间复杂度都是O（logn）。但是，数组的实现还是更高效一些，因为在addElement操作中数组实现不用去确定插入双亲的结点，在removeElement操作中数组实现不需要确定新的最末一片叶子。

private HeapNode<T> getNextParentAdd()
    
        HeapNode<T> result = lastNode;

        while ((result != root) && (result.getParent().getLeft() != result))
            result = result.getParent();

        if (result != root)
            if (result.getParent().getRight() == null)
                result = result.getParent();
            else
            
                result = (HeapNode<T>)result.getParent().getRight();
                while (result.getLeft() != null)
                    result = (HeapNode<T>)result.getLeft();
            
        else
            while (result.getLeft() != null)
                result = (HeapNode<T>)result.getLeft();
          
        return result;
    

201723282018-2019《java软件结构与数据结构》第九周学习总结(代码片段)

201723282018-2019《Java软件结构与数据结构》第九周学习总结概述Generalization本周学习了无向图、有向图、带权图、常用的图算法、图的实现策略。教材学习内容总结Asummaryoftextbook图（graph）与树类似，图由结点和这些结点之间的连... 查看详情

201723282018-2019《java软件结构与数据结构》第八周学习总结(代码片段)

201723282018-2019《Java软件结构与数据结构》第八周学习总结概述Generalization本周学习了二叉树的另一种有序扩展？是什么呢？你猜对了！ヾ(?°?°?)??就是堆。本章将讲解堆的链表实现and数组实现，以及往堆中添加元素或从堆中删除... 查看详情

201723282018-2019《java软件结构与数据结构》第六周学习总结(代码片段)

201723282018-2019《Java软件结构与数据结构》第六周学习总结概述Generalization本周学习了第十章：非线性集合与数据结构--树。主要讨论了树的使用和实现，以及考察实现和使用树的实例。教材学习内容总结Asummaryoftextbook树（tree）：... 查看详情

201723282018-2019《java软件结构与数据结构》第七周学习总结(代码片段)

201723282018-2019《Java软件结构与数据结构》第七周学习总结概述Generalization本周学习了第11章：二叉查找树。在本章中，主要探讨了二叉查找树的概念和各种二叉查找树实现，考察为二叉查找树添加和删除元素的算法以及维护平衡... 查看详情

java示例代码_爬上TypeMirror对象的层次结构树

java示例代码_爬上TypeMirror对象的层次结构树 查看详情

Java 套接字提前结束流

】Java套接字提前结束流【英文标题】：Javasocketgivingprematureendofstream【发布时间】：2011-02-0216:21:44【问题描述】：我正在设置一个连接到XMPP服务器的彗星服务器。以下是它的下降方式：客户端与Comet服务器连接，并且打开了一个... 查看详情

java -version，关于三个不同结果行的问题

】java-version，关于三个不同结果行的问题【英文标题】：java-version,questionaboutthreedifferentresultlines【发布时间】：2021-11-1908:56:03【问题描述】：我用Java编程已经有一段时间了，但实际上从来没有太在意版本控制。但是现在我检查... 查看详情

jmeter-察看结果树-响应数据，中文显示乱码问题处理

...t.encoding=utf-8修改配置后，重启生效 by：虾米 北京软件测试QQ1群:507088 北京软件测试跳槽群:450569 北京软件测试QQ2群：132142000 查看详情

logging模块全总结(代码片段)

...信息参考文档一、日志相关概念日志是一种可以追踪某些软件运行时所发生事件的方法。软件开发人员可以向他们的代码中调用日志记录相关的方法来表明发生了某些事情。一个事件可以用一个可包含可选变量数据的消息来 查看详情

java实现飞机大战小游戏|java入门结课作业(代码片段)

...据目录寻找自己需要的段落导语：本博客为个人整理Java学习记录帖，如有错误，感谢指正。系统学习，欢迎持续关注，后续陆陆续续更新Java后端项目，Java部分我不打算更新基础部分知识，会从JavaWeb开... 查看详情

jmeter——查看结果树——html使用

            ========================================================================================================     查看详情

java中&&和?表达式结合时会出现的坑

　　首先是背景，刚放假回家比较闲，就把以前写了一些算法题的一个项目拿出来继续写，想把其中的插入排序修改成支持升序和降序的，然后就出现了这个坑，具体是这样的：　　先把插入排序的代码摆出来吧。/***插入排序*@... 查看详情

如何正确迭代所有 BigQuery 结果行？

...给了我245217个结果，我可以在浏览器控制台。根据示例在Java 查看详情

java学习多线程：线程创建线程状态线程同步线程通信全总结(代码片段)

目录1、基本概念2、线程创建2.1、继承Thread类（重点）ThreadAPI2.2、实现Runnable接口（重点）Runnable接口API以上两种方式的比较：初识并发问题——买火车票龟兔赛跑问题：img2.3、实现Callable接口（了解ÿ... 查看详情

北航大讲堂结课报告

...过程中，突破外国技术垄断已经是势在必行。然而在航空软件方面还有许多问题等待我们去解决。2.   我国航空航天产业现状随着我国国民经济的持续发展和人民生活水平的不断提高，航空运输行业在国家经济、社会... 查看详情

java学习网络编程全总结——tcpudp多线程io流socket简易在线咨询聊天室java爬虫(代码片段)

...误区trimstartsWith在线咨询：两个人都可以发送1.8、URLJava爬虫----爬取网易 查看详情

对软件工程课程的期望

博文中将包含课程结课后学习到的能力的预期,对课程的期望,对课程项目的愿景规划：一、课程结课后学习到的能力的预期：　　1.加强自身的领导力、影响力　　2.可以增强与他人的协作能力和团队的领导能力　　3.提高自己的... 查看详情

数据结结构(代码片段)

...结构=程序+算法</font>数据结构有什么用当我们使用着java官方给你提供的容器的时候，我们用起来是非常方便的，ArrayList其实是一个无线扩充的数据LinkedList其实是一个链表。现实世界中存储数据，我们要通过一些工具或者建... 查看详情