数据结构-堆

堆：
    优先队列（Priority Queue）：特殊的“队列”，取出元素的顺序是 依照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序
    
    优先队列可以用完全二叉树表示：
    两个特性：
        结构性：用数组表示的完全二叉树
        有序性：任一结点的关键字是其子树所有结点的最大值(或最小值) 
            “最大堆(MaxHeap)”,也称“大顶堆”：最大值 
            “最小堆(MinHeap)”,也称“小顶堆” ：最小值 
        从根结点到任意结点路径上结点序列的有序性！ 
    
堆的抽象数据类型描述 
    类型名称：最大堆（MaxHeap)    
    数据对象集：完全二叉树，每个结点的元素值不小于其子结点的元素值 
    
    操作集：最大堆H ? MaxHeap，元素item ? ElementType，主要操作有： 
    •MaxHeap Create( int MaxSize )：创建一个空的最大堆。 •
    Boolean IsFull( MaxHeap H )：判断最大堆H是否已满。 
    •Insert( MaxHeap H, ElementType item )：将元素item插入最大堆H。 
    •Boolean IsEmpty( MaxHeap H )：判断最大堆H是否为空。 
    •ElementType DeleteMax( MaxHeap H )：返回H中最大元素(高优先级)。 
    
哈夫曼树：
    定义：最优二叉树或哈夫曼树: WPL最小的二叉树
    带权路径长度(WPL)：设二叉树有n个叶子结点，每个叶子结点带 有权值 w，
        从根结点到每个叶子结点的长度为 l，则每个叶子结 点的带权路径长度之和就是：所有叶子节点的l*w的和
    
    
哈夫曼树的构造 ：每次把权值最小的两棵二叉树合并 

哈夫曼树的特点: 
    没有度为1的结点；
    n个叶子结点的哈夫曼树共有2n-1个结点；
    哈夫曼树的任意非叶节点的左右子树交换后仍是哈夫曼树；     
    同一权值可对应多个不同构成的哈夫曼树
    
集合及运算 ：
    并查集：集合并、查某元素属于什么集合 
    并查集问题中集合存储如何实现？ 
        可以用树结构表示集合，树的每个结点代表一个集合元素 
        采用数组存储形式 ，数组中每个元素均有一个属性parent存储其父节点的下标
        根节点的父节点可以设置为一个可以标识根节点的值，如-1等
    
    查找某个元素所在的集合：//由根节点决定
        即找到根节点，根据父节点一直找下去，直到找到根节点
        
        
    集合的并运算 ：
        分别找到X1和X2两个元素所在集合树的根结点 
        如果它们不同根（说明X1,X2不在同一个集合中），则将其中一个根结点的父结点指针设置成 另一个根结点的数组下标