自己动手实现java数据结构（八） 优先级队列

　　上滤操作时，上滤元素进行比较的次数正比于上滤元素的深度。因此，上滤操作的时间复杂度为O(logN)。

    @Override
     insert(E newData) {
         先插入新数据到 向量末尾
        .innerArrayList.add(newData);

         获得向量末尾元素下标
        int lastIndex = getLastIndex();
         对向量末尾元素进行上滤，以恢复堆序性
        siftUp(lastIndex);
    }

   
     * 上滤操作
     *  index 需要上滤的元素下标
     * void siftUp( index){
        while(index >= 0 获得当前节点
            int parentIndex = getParentIndex(index);

            E currentData = .innerArrayList.get(index);
            E parentData = .innerArrayList.get(parentIndex);

             如果当前元素 大于 双亲元素
            if(compare(currentData,parentData) > 0){
                 交换当前元素和双亲元素的位置
                swap(index,parentIndex);

                 继续向上迭代
                index = parentIndex;
            }{
                 当前元素没有违反堆序性，直接返回
                ;
            }
        }
    }

3.4 删除和下滤

　　当优先级队列中极值元素出队时，需要在满足堆序性的前提下，选出新的极值元素。

　　我们简单的将当前向量末尾的元素放在堆顶，堆序性很有可能被破坏了。此时，我们需要对当前的堆顶元素进行一次下滤操作，使得整个完全二叉堆恢复堆序性。

下滤操作：

　　下滤的元素不断的和自己的左、右孩子节点进行优先级的比较：

　　1. 双亲节点最大，堆序性恢复，终止下滤。

　　2.?左孩子节点最大，当前下滤节点和自己的左孩子节点交换，继续下滤。

　　3.?右孩子节点最大，当前下滤节点和自己的右孩子节点交换，继续下滤。

　　4.?特别的，当下滤的元素抵达堆底时(成为叶子节点)，堆序性已经恢复，终止下滤。

下滤操作时间复杂度：

　　下滤操作时，下滤元素进行比较的次数正比于下滤元素的高度。因此，下滤操作的时间复杂度为O(logN)。

 E popMax() {
        .innerArrayList.isEmpty()){
            throw new CollectionEmptyException("当前完全二叉堆为空");
        }

         将当前向量末尾的元素和堆顶元素交换位置
         getLastIndex();
        swap(0,lastIndex);

         暂存被删除的最大元素（之前的堆顶最大元素被放到了向量末尾）
        E max = .innerArrayList.get(lastIndex);
        this.size-- 对当前堆顶元素进行下滤，以恢复堆序性
        siftDown(0);

         max;
    }

  
     * 下滤操作
     *  index 需要下滤的元素下标
     * void siftDown(int size = .size();
         叶子节点不需要下滤
        int half = size >>> 1while(index < half){
            int leftIndex = getLeftChildIndex(index);
            int rightIndex = getRightChildIndex(index);

            if(rightIndex < size){
                 右孩子存在 (下标没有越界)

                E leftData = .innerArrayList.get(leftIndex);
                E rightData = .innerArrayList.get(rightIndex);
                E currentData = .innerArrayList.get(index);

                 比较左右孩子大小
                if(compare(leftData,rightData) >= 0){
                     左孩子更大，比较双亲和左孩子
                    ){
                         双亲最大，终止下滤
                        ;
                    }{
                         三者中，左孩子更大，交换双亲和左孩子的位置
                        swap(index,leftIndex);
                         继续下滤操作
                        index = leftIndex;
                    }
                }{
                     右孩子更大，比较双亲和右孩子
                     三者中，右孩子更大，交换双亲和右孩子的位置
 rightIndex;
                    }
                }
            } 右孩子不存在 (下标越界)
.innerArrayList.get(leftIndex);
                E currentData =  当前节点 大于 左孩子
                 终止下滤
                    ;
                } 交换 左孩子和双亲的位置
                    swap(index,leftIndex);
                     继续下滤操作
                    index = leftIndex;
                }
            }
        }
    }

3.5?批量元素建堆

　　有时，我们需要将一个无序的元素集合数组转换成一个完全二叉堆，这一操作被称为批量建堆。

　　一个朴素的想法是：将无序集合中的元素依次插入一个空的完全二叉堆，对每一个新插入的元素进行上滤操作。使用上滤操作实现的对N个元素进行批量建堆的算法，其时间复杂度为O(n.logn)，比较直观。

　　但还存在一种效率更加高效的批量建堆算法，是以下滤操作为基础实现的，被称为Floyd建堆算法。下滤操作可以看做是将两个较小的堆合并为一个更大堆的过程(单个元素可以被视为一个最小的堆)，通过从底到高不断的下滤操作，原本无序的元素集合将通过不断的合并建立较小的堆，最终完成整个集合的建堆过程。

　　Floyd建堆算法的时间复杂度的证明较为复杂，其时间复杂度比起以上滤为基础的朴素算法效率高一个数量级，为O(n)。

（编辑：我爱故事小小网_铜陵站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!