`
iluoxuan
  • 浏览: 583079 次
  • 性别: 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

 

 

 

分享到:
评论

相关推荐

    大根堆(小根堆)实现-优先队列

    这些特性使得堆成为实现优先队列的理想选择。 **大根堆与小根堆** 大根堆和小根堆是堆的两种基本类型。大根堆中,根节点总是集合中最大(或最小)的元素,确保了在任何时候,堆顶的元素都是最大的。相反,小根堆的...

    用数组实现的优先队列(JAVA)

    数组实现优先队列的核心思想是维护一个最小堆(最小堆是堆数据结构的一种,每个父节点的值都小于或等于其子节点的值)。插入元素时,将元素放在数组的末尾,然后通过上浮操作调整堆以保持最小堆性质。删除队首元素...

    堆与堆排序.ppt

    2. 优先队列:堆可以用来实现优先队列,例如 Job Scheduling、Resource Allocation等。 3. 图算法:堆可以用来解决图论问题,例如最短路径、最小生成树等。 堆和堆排序是一种重要的数据结构和算法,广泛应用于...

    堆排序,构建最优队列

    堆排序是一种基于比较的排序算法...`Heap.java`文件可能是实现堆排序或优先队列的一个Java源代码文件,可能包含了上述讨论的堆构造、插入、删除等相关方法。你可以通过阅读和理解这个文件来深入学习堆排序的实现细节。

    优先队列-java可以选择属性和升序降序

    优先队列在Java编程中是一种特殊的数据结构,它遵循特定的出队顺序,通常是最小元素(最小优先队列)或最大元素(最大优先队列)先出队。这种数据结构在解决各种问题时非常有用,例如任务调度、事件驱动编程、搜索...

    堆排序,插入排序和优先对排序的运行时间的比较

    优先队列排序的效率与堆排序相当,其操作如插入、删除最小元素(或最大元素)的时间复杂度为O(log n)。优先队列排序适用于需要频繁查找最大或最小元素,且需动态插入和删除元素的场景。 在C/C++环境中,VC++编译器...

    优先队列、图等总结及习题.docx

    1. 堆排序:使用优先队列实现堆排序算法。 2. 哈夫曼编码:使用优先队列实现哈夫曼编码算法。 四、图的定义和实现 1. 图的定义:图是用线或边连接在一起的顶点或节点的集合,记为 G = (V,E),其中 V 是顶点集,E ...

    广东工业大学-优先队列和二叉堆.pdf

    二叉堆的性质使得其在实现优先队列时非常高效,特别是插入(Insert)和删除最大(或最小)元素(RemoveMax 或 RemoveMin)操作的时间复杂度可以保持在对数时间内,即O(log n)。 在课程中提到的具体问题解决实例包括...

    小大根交替堆实现双端优先队列

    总的来说,这个项目通过小大根交替堆实现的双端优先队列,结合学生信息,可以高效地处理学生成绩的查询、排序和管理,尤其是在需要快速获取最高分和最低分的情况下。这种数据结构的设计和实现对于学习数据结构和算法...

    C语言数据结构优先队列实现

    对整个优先队列执行堆排序,首先从最后一个非叶子节点开始自底向上调整,构建小顶堆,然后将堆顶元素与末尾元素交换,删除堆顶元素,重复这个过程,直至整个队列有序。 7. `SSearchElem`和`SSearchWeigth`函数: ...

    看图聊算法:堆排序,我们学习它可能并不是为了排序.pdf

    优先队列作为堆排序的一个经典应用场景,常用于需要高效处理数据的场合,如操作系统中的进程调度、事件驱动系统中处理高优先级任务等。此外,堆排序在解决Top-K问题中也发挥着重要作用,即在大数据集中快速找到前K个...

    优先队列算法实现(Java)

    - Java的`java.util.PriorityQueue`是优先队列的实现,它基于二叉堆(通常是最小堆),满足堆的性质:父节点的优先级总是不小于子节点。 - PriorityQueue支持`add()`、`offer()`、`peek()`、`poll()`等方法,分别...

    优先队列(Priority Queue)是一种特殊类型的队列

    堆是一种完全二叉树,满足堆性质:父节点的键值总是大于或等于(最小优先队列)或小于或等于(最大优先队列)其子节点的键值。这样可以确保根节点始终是最小或最大元素,从而方便快速地执行Extract-Min或Extract-Max...

    priority_queue_1.0_excitingfbh_matlab优先队列_matlab优先队列_优先队列_

    1. **数组实现**:基础的数据结构可以是一个动态调整大小的数组,使用堆排序的思想来维护优先级。最小堆或最大堆是最常见的选择,前者保证队列顶部总是最小值,后者则是最大值。 2. **链表实现**:另一种方法是使用...

    数据结构课程设计优先队列数据(priority_queue)类型

    3. **堆排序**:使用优先队列进行快速排序。 4. **最短路径问题**:解决单源最短路径问题,如Prim算法和Kruskal算法。 在实际项目中,通过理解和熟练掌握优先队列数据类型,我们可以解决很多复杂的问题,提高算法...

    堆排序算法简单实现

    堆排序是一种基于比较的排序算法,它通过构造一个大顶堆或小顶堆来实现排序。在大顶堆中,每个父节点的值都大于或等于其子节点的值;在小顶堆中,父节点的值小于或等于子节点的值。这种数据结构类似于一个完全二叉树...

    优先队列是一种数据结构.pdf

    3. **堆排序:** 堆排序算法利用优先队列(通常是最大堆),通过反复从堆中取出最大元素并将其放到序列的末尾,实现对序列的升序排序。 4. **事件模拟:** 在模拟事件驱动的系统时,优先队列用于管理事件的触发顺序...

    基于vc的堆、最大优先队列源码

    在本文中,我们将深入探讨基于VC的堆和最大优先队列的实现,这些实现是通过C++编程语言完成的。堆是一种特殊的树形数据结构,它满足特定的性质,如最大堆或最小堆,常被用于优化算法和解决各种问题。在VC(Visual ...

    数组堆操作,包括堆排序、堆插入、堆删除等

    这种数据结构常用于优先队列的实现,因为它可以快速找到最大或最小元素。 1. 堆排序:堆排序是一种高效的排序算法,基于比较排序,其时间复杂度为O(n log n)。基本步骤包括构建初始堆、交换堆顶元素(最大元素)与...

    快速排序、堆排序、归并排序、希尔排序实现

    堆可以看作是一个近似最大或最小元素的优先队列。在C++中,可以使用标准库中的`std::make_heap`、`std::push_heap`、`std::pop_heap`和`std::sort_heap`等函数来实现堆排序。 **归并排序(Merge Sort)** 归并排序...

Global site tag (gtag.js) - Google Analytics