`
iluoxuan
  • 浏览: 569166 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

4:堆排序实现的最小优先队列

 
阅读更多

1:  优先队列

 

不是先进先出,是按照冒个规则,出:

 

2: 堆排序

   1: 建堆

   2: 堆顶与最后一个节点调换,堆顶出堆,重新调整堆

 

    小顶堆:  节点i< 2i(左孩子) && i< 2i+1 (右孩子) 

     建立堆:(递归)当前i节点 和i/2 比较 如果i小于i/2 交换

    调整堆:  顶点开始 ,(去左右节点中最小的)比较 ,若 孩子节点小 继续递归 

                    若 孩子节点大 退出 (因为本身已经是堆排序的)

 

 

package com.algorithm.common;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * 堆排序的最小优先队列
 * @author lijunqing
 */
public class MinPQ<Key> implements Iterable<Key> {

    private Key[] pq;

    private int N;

    public MinPQ() {
        this(1);
        N=0;
    }

    public MinPQ(int initCapacity) {
        pq=(Key[])new Object[initCapacity + 1];
        N=0;
    }

    /**
     * 插入一个节点
     * @param key
     */
    public void insert(Key key) {
        if(N == pq.length - 1) {
            resize(2 * pq.length);
        }
        N++;
        pq[N]=key;
        swim(N);
    }

    /**
     * 堆顶和最后一个节点交互 堆顶出堆 从堆顶开始调整堆
     * @return
     */
    public Key delMin() {
        exch(1, N);
        Key min=pq[N];
        pq[N]=null;
        N--;
        skin(1); // 调整堆
        return min;
    }

    /**
     * 从i节点开始调整堆
     * @param i
     */
    private void skin(int i) {

        while(2 * i <= N) {
            int k=2 * i;
            if(k < N && greater(k, k + 1)) { // 比较右节点小 取右节点
                k++;
            }
            if(greater(k, i)) { // 如果孩子节点大 不需要调整了
                break;
            }
            exch(i, k);
            i=k;
        }
    }

    /**
     * 递归交互子父节点
     * @param i
     */
    private void swim(int i) {
        while(i > 1 && greater(i / 2, i)) {
            exch(i, i / 2);
            i=i / 2;
        }
    }

    /**
     * 交互节点值
     * @param i
     * @param j
     */
    private void exch(int i, int j) {
        Key temp=pq[i];
        pq[i]=pq[j];
        pq[j]=temp;
    }

    /**
     * 子节点小于父节点 [key是带有compare的] 只能现在用的数字
     * @param i
     * @param i2
     * @return
     */
    private boolean greater(int i, int j) {
        return ((Comparable<Key>)pq[i]).compareTo(pq[j]) > 0;
    }

    /**
     * 重新申请空间
     * @param capacity
     */
    private void resize(int capacity) {
        Key[] temp=(Key[])new Object[capacity];
        for(int i=0; i < pq.length; i++) {
            temp[i]=pq[i];
        }
        pq=temp;
    }

    public int size() {
        return N;
    }

    public boolean isEmpty() {
        if(N == 0) {
            return true;
        }
        return false;
    }

    @Override
    public Iterator<Key> iterator() {
        return new HeapIterator();
    }

    private class HeapIterator implements Iterator<Key> {

        // 重新建一个
        private MinPQ<Key> copy;

        public HeapIterator() {
            copy=new MinPQ<Key>(size());
            for(int i=1; i <= N; i++)
                copy.insert(pq[i]);
        }

        public boolean hasNext() {
            return !copy.isEmpty();
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }

        public Key next() {
            if(!hasNext())
                throw new NoSuchElementException();
            return copy.delMin();
        }
    }

    public static void main(String[] agrs) {
        MinPQ<Integer> minPQ=new MinPQ<Integer>();
        minPQ.insert(25);
        minPQ.insert(6);
        minPQ.insert(9);
        minPQ.insert(10);
        minPQ.insert(3);
        minPQ.insert(23);

        Iterator<Integer> m=minPQ.iterator();
        while(m.hasNext()) {
            System.out.println(m.next());
        }

    }

}

 

 结果:

  3

6

9

10

23

25

 

 

 

分享到:
评论

相关推荐

    排序、树、图、数值算法大全

    堆排序 快速排序 2、树算法 红黑树 B树 3、图算法 深度优先周游 广度优先周游 队列拓扑排序 深度优先搜索拓扑 单源最短路径 每对顶点最短距离 最小支撑树PRIM 最小支撑树KRUSKAL 3、数值及其他: 马踏棋盘贪心启发...

    排序、树、图、数值算法UI

    堆排序 快速排序 2、树算法 红黑树 B树 3、图算法 深度优先周游 广度优先周游 队列拓扑排序 深度优先搜索拓扑 单源最短路径 每对顶点最短距离 最小支撑树PRIM 最小支撑树KRUSKAL 3、数值及其他: 马踏棋盘贪心启发...

    leetcode23合并k个有序链表。优先队列(最小堆)python 代码+思路

    三种方法:暴力、分治、最小堆(优先队列) 暴力解法有两种,一种是12排,然后和3,然后和4,继续下去; 另一种是先放到一个数组中进行排序,然后按照顺序连接 分而治之:两两合并 如果有k个链表,平均每个链表有n个...

    Java数据结构与算法视频教程

    视频详细讲解,需要的小伙伴自行网盘下载,链接见附件... 优先队列; 2-3查找树; 红黑树;第五章: B-树; B+树; 并查集; 无向图;第六章: 有向图; 拓扑排序; 加权无向图; 最小生成树; 加权有向图; 最短路径;

    Delphi算法与数据结构 源码(上)

    优先队列和堆排序 9.1优先队列 9.2堆 9.3堆排序 9.4扩展优先队列 9.5小结 第10章 状态机和正则表达式 10.1状态机 10.2正则表达式 10.3小结 第11章数据压缩 11.1数据表示 11.2数据压缩 11.3位流 11.4最小...

    Delphi算法与数据结构 源码(下)

    优先队列和堆排序 9.1优先队列 9.2堆 9.3堆排序 9.4扩展优先队列 9.5小结 第10章 状态机和正则表达式 10.1状态机 10.2正则表达式 10.3小结 第11章数据压缩 11.1数据表示 11.2数据压缩 11.3位流 11.4最小...

    C++实现最小生成树之普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法

    知识点: ...6、优先队列priority_queue的自定义排序 7、大根堆、小根堆的区别 8、结构体的构建 面向对象: 有一定C++基础,学习数据结构及算法的朋友。 有不足之处,欢迎大家留言批评指正,我们共同进步。

    数据结构和算法:各种数据结构和算法的实现-链表,堆栈,队列,二进制搜索树,AVL树,红黑树,特里,图算法,排序算法,贪婪算法,动态编程,段树等等

    气泡排序堆排序插入排序合并排序快速排序选择排序 二进制搜索树 插入删除中预定遍历顺序遍历后遍历级别顺序遍历查找二叉搜索树的高度检查树是否为二叉搜索树(2种方法) 在二分搜索树中查找最大和最小元素 AVL树 ...

    Algorithms in C 1至5册 中文版

    包括基本算法分析原理,基本数据结构、抽象数据结构、递归和树等数据结构知识,选择排序、插入排序、冒泡排序、希尔排序、快速排序方法、归并和归并排序方法、优先队列与堆排序方法、基数排序方法以及特殊用途的排序...

    DataStructureDeepImpl:基于Java的数据结构深度实现(通用实用程序)

    SP 散列堆(优先堆) 二叉堆二项式堆D堆斐波那契堆索引堆左派堆对堆队列基于数组的队列基于链表的队列阻塞队列循环队列具有最大值的队列具有最小值的队列使用两个堆栈实现的队列队列排序一个阵列中的三个队列堆基于...

    扩展矩阵leetcode-algorithms:算法

    堆/优先队列/堆排序: , , 后缀自动机: , , , , , , 最低共同祖先: , , , 计数反转: , , , Euclid 的扩展算法: 后缀树: , , , , , , 动态规划:来自 clrs(essential), , , , , , , , 的章节 基本数据结构: , ,...

    leetcode分类-leetcode:练习leetcode题目,提高编程能力

    排序算法:快速排序、归并排序、计数排序 搜索算法:回溯、递归、深度优先遍历,广度优先遍历,二叉搜索树等 图论:最短路径、最小生成树 动态规划:背包问题、最长子序列 数据结构,主要有如下几种: 数组与链表:...

    数据结构和算法动画演示

    堆排序 希儿排序 桶式排序法 基数排序 二叉树的建立 二叉排序树的生成 二叉排序树的删除 中序线索化二叉树 寻找中序线索化二叉树指定结点的前驱 寻找中序线索化二叉树指定结点的后继 构造哈夫曼树的算法模拟 构造...

    PHP SPL标准库之数据结构堆(SplHeap)简单使用实例

    堆(Heap)就是为了实现优先队列而设计的一种数据结构,它是通过构造二叉堆(二叉树的一种)实现。根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。二叉堆还常用于排序(堆排序)。 如下:最小堆...

    数据结构PPT文件

    22堆排序与优先队列.pptx 23快速排序.pptx 24归并排序.pptx 25桶基计排序.pptx 26查找概念与顺序查找.pptx 27折半与分块查找.pptx 28二叉查找树.pptx 29哈希概念函数及冲突.pptx 30哈希的应用.pptx 31八数码问题启发...

    欧拉公式求圆周率的matlab代码-PHP-Data-Structure-and-Algorithms:使用PHP实现不同数据结构和算法实现的

    优先队列 循环队列 双端队列-解除队列 树木 通用树 二叉树 二进制搜索树 树遍历(有序,有序,有序) 特里(简单的插入和搜索操作) 堆 最小堆 最大堆 图形 BFS 贝尔曼福特算法 DFS 迪克斯特拉 弗洛伊德·沃霍尔 ...

    数据结构(C语言版)\Java数据结构和算

    7.6 堆排序 7.7 多关键字排序 7.8 链表排序和索引表排序 7.9 内部排序小结 7.10 外部排序 7.11 参考文献和选读材料 第8章 Hash法 8.1 引言 8.2 静态Hash法 8.3 动态Hash法 8.4 Bloom滤波器 8.5 参考文献...

    leetcode刷完300题-leetcodeSource:leetcode日刷一道

    排序算法:快速排序、归并排序、计数排序 搜索算法:回溯、递归、深度优先遍历,广度优先遍历,二叉搜索树等 图论:最短路径、最小生成树 动态规划:背包问题、最长子序列 数据结构: 数组与链表:单 / 双向链表 栈...

    基础算法源码、算法基础

    冒泡排序、快速排序、计数排序、合并排序、希尔排序、选择排序、最优二叉查找树、蛮力法字符串匹配、二叉树基本算法(插入、查找、删除、遍历)、队列的使用、堆栈的使用、堆与堆排序、背包问题、图的拓扑排序、图...

    数据结构讲义(严蔚敏版)(含算法源码)

    数据结构讲义(严蔚敏版)(含算法源码) 1. 经典算法 单链表:遍历、插入、删除 循环队列:队列空、队列...堆的概念,调整成堆(A),堆排序(A,O) 归并排序(A,O) 链式基数排序(A,O) 各种排序算法的对比结论(O)

Global site tag (gtag.js) - Google Analytics