jjzjj

堆的 shift up

runoob 2023-04-06 原文

堆的 shift up

本小节介绍如何向一个最大堆中添加元素，称为 shift up。

假设我们对下面的最大堆新加入一个元素52，放在数组的最后一位，52大于父节点16，此时不满足堆的定义，需要进行调整。

首先交换索引为 5 和 11 数组中数值的位置，也就是 52 和 16 交换位置。

此时 52 依然比父节点索引为 2 的数值 41 大，我们还需要进一步挪位置。

这时比较 52 和 62 的大小，52 已经比父节点小了，不需要再上升了，满足最大堆的定义。我们称这个过程为最大堆的 shift up。

Java 实例代码

源码包下载：Download

src/runoob/heap/HeapShiftUp.java 文件代码：

package runoob.heap;

/**
 * 往堆中添加一元素
 */
public class HeapShiftUp<T extends Comparable> {

    protected T[] data;
    protected int count;
    protected int capacity;

    // 构造函数, 构造一个空堆, 可容纳capacity个元素
    public HeapShiftUp(int capacity){
        data = (T[])new Comparable[capacity+1];
        count = 0;
        this.capacity = capacity;
    }
    // 返回堆中的元素个数
    public int size(){
        return count;
    }

    // 返回一个布尔值, 表示堆中是否为空
    public boolean isEmpty(){
        return count == 0;
    }
    // 像最大堆中插入一个新的元素 item
    public void insert(T item){
        assert count + 1 <= capacity;
        data[count+1] = item;
        count ++;
        shiftUp(count);
    }
    // 交换堆中索引为i和j的两个元素
    private void swap(int i, int j){
        T t = data[i];
        data[i] = data[j];
        data[j] = t;
    }

    //********************
    //* 最大堆核心辅助函数
    //********************
    private void shiftUp(int k){

        while( k > 1 && data[k/2].compareTo(data[k]) < 0 ){
            swap(k, k/2);
            k /= 2;
        }
    }

    // 测试 HeapShiftUp
    public static void main(String[] args) {
        HeapShiftUp<Integer> heapShiftUp = new HeapShiftUp<Integer>(100);
        int N = 50; // 堆中元素个数
        int M = 100; // 堆中元素取值范围[0, M)
        for( int i = 0 ; i < N ; i ++ )
            heapShiftUp.insert( new Integer((int)(Math.random() * M)) );
        System.out.println(heapShiftUp.size());

    }
}
shiftupspanstylecolor【数据结构与算法

有关堆的 shift up的更多相关文章

  1. c++ - 为什么堆的数量总是1？ - 2

    我正在使用WinDbg查看进程中的堆数，方法是dt_PEB@$peb。我得到以下信息，+0x088NumberOfHeaps:1现在根据AdvancedWindowsDebugging一书，Mostapplicationsimplicitlyusecomponentsthatcreatetheirownheaps.AgreatexampleistheCruntime,whichcreatesitsownheapduringinitialization.我在main处添加了断点，但我仍然可以看到只有一个堆在处理中。其次，我运行了以下代码，堆的数量仍然是1。BYTE*pAlloc1=NUL

  2. c++ - 什么时候使用HeapCreate函数或者什么情况下需要堆的数量？ - 2

    WindowsAPI有一组用于堆创建和处理的函数:HeapCreate、HeapAlloc、HeapDestroy等。我想知道程序中另一个堆有什么用？从碎片的角度来看，您将获得外部碎片，其中内存未在堆之间重用。所以即使使用低碎片堆，仍然存在碎片。附加堆的内存管理似乎是低级的。所以它们不容易使用。此外，可以使用从堆分配和管理分配的内存来模拟额外的堆。那么有什么用呢？你用过吗？ 最佳答案 一个用例可能是一个长时间运行的复杂进程，它执行大量内存分配和释放。如果用户想要中断进程，那么清理当前分配的内存的一种简单方法可能是将所有内容都放在私有

  3. java - 堆的算法 - 2

    试图重现Heap的算法，以生成整数数组的所有可能排列，但我无法解决除三个以外的其他整数的问题。Heap的算法来自维基百科:proceduregenerate(N:integer,data:arrayofany):ifN=1thenoutput(data)elseforc:=1;c我的代码:publicstaticvoidperm(int[]list,intn){if(n==1){System.out.println(Arrays.toString(list));}else{for(intc=1;c我做错了什么和误解了它？为什么它仅适用于[1,2,3](n=3)作为输入，而不适用于n=2

  4. java - 您可以创建(Oracle JVM)java 堆的最小值是多少？ - 2

    java愉快地接受-Xmx1k作为参数，但“实验表明”这仍然是一个8MB的堆。谷歌搜索没有找到任何可用的东西，所以我想知道，您可以在Java中强制要求的最小堆大小是多少？谢谢，埃里克编辑:它似乎因平台和Java版本而略有不同。在我的Mac上，使用1.6.0_24，我可以正确配置它的最小值是:$java-Xms1k-Xmx4097k-XX:NewSize=192k-cp.Foo5636096或大约5.375M，其中Foo.java只是:publicclassFoo{publicstaticvoidmain(String[]args){System.out.println(Runtime.

  5. java - 最大 jvm 堆的大小未达到或接近机器上的最大物理内存的原因是什么？ - 2

    我有一台64位机器，理论上地址空间是2^64字节，它有32G的物理RAM。这是一台具有16个内核的服务器级机器，是一台生产服务器。既然没有其他消耗大量内存的进程在运行，并且服务器jvm是唯一正在运行的应用程序，是否有任何理由不将jvm堆设置为非常大的数字？我看到它被设置为少于10场演出，但没有任何我能想到的解释。正如我之前在帖子中提到的:我知道内核、缓存和其他进程需要共享RAM。但是除了任何其他进程和操作系统原生的东西，没有其他事情发生。这台机器是一台生产机器，专门用于这个特定的jvm。是否有任何理由不设置为20gigs/32g(物理内存)？从下面的评论来看——似乎不是……除了需要快速

  6. java - Java 堆的大 NewSize 使进程长时间无响应 - 2

    我有java应用程序，它可以使用特定的内存来完成一些工作。我注意到，当我开始应用程序时，将近80%的堆设置用于年轻一代，我的应用程序运行速度比默认1:2设置快得多。特别是，我启动jvm时:java-XX:NewSize=10G-XX:+UseParallelOldGC-server-Xmx12G-Xms12G服务器至少有14Gb的可用物理内存，因此我认为对于Java堆和“其他”空间来说应该足够了。现在事情是这样的:25.289:[GC[PSYoungGen:7872317K->1058813K(9175040K)]7872533K->1059029K(11272192K),0.1876

  7. java - 如何获取Java堆的内存地址？ - 2

    如何确定当前进程中运行的JVM的Java堆在内存中的地址？也就是说，使用Java、C或其他调用获取一个void*指针或等效于JVM为堆分配的连续内存区域？Matlab在其进程中嵌入了一个JVM。JVM分配的内存不可用于Matlab数组，其中，堆很重要，因为它占用了一大块连续的内存并且从不收缩，而Matlab的数组也需要连续的内存。如果在扩展期间重新分配堆，可能会导致碎片。我想检测我的进程来检查Java堆和Matlab的内存View之间的交互，并找出它何时因调整大小而移动，最好是在进程内。这需要堆的地址。从java.lang.Runtime很容易找到堆大小，但不是它在内存中的地址。如何做

  8. java - 我可以让 Tomcat 作为转储堆的服务运行吗？ - 2

    我正在尝试让Tomcat(目前作为服务在Windows2003机器上运行)在OutOfMemoryError上转储堆。(Tomcat正在运行Hudson，它在我构建的尾端报告堆空间问题。手动运行构建不会产生此类错误。Hudson人员需要堆转储才能开始。)按照其他地方的说明，我已经告诉Apache服务监视器配置它用来运行Tomcat的JVM，以便在遇到OutOfMemoryError时通过将以下内容添加到JVM选项来转储堆:-XX:+HeapDumpOnOutOfMemoryError然后我再次运行构建。果然，它报告存在堆错误。我扫描整个磁盘寻找默认的java_pid123.hprof文

  9. c++ - 混淆了堆的两种不同实现 - 2

    函数一voidmin_heapify(intarr[],intn,inti){intj,temp;temp=arr[i];j=2*i;while(j=arr[j]){arr[j/2]=arr[j];j=2*j;}}arr[j/2]=temp;}函数二voidmax_heapify(intarr[],intn,inti){intlargest=i;//Initializelargestasrootintl=2*i+1;//left=2*i+1intr=2*i+2;//right=2*i+2//Ifleftchildislargerthanrootif(l问题详情这里堆化的工作方式与创建m

  10. 堆的 C++ 损坏 - 2

    我有一个简单的同步队列templateclassSynchronisedQueue{public:voidEnqueue(constT&data){boost::unique_locklock(queueMutex);dataQueue.push(data);conditionVariable.notify_one();}TDequeue(){boost::unique_locklock(queueMutex);while(dataQueue.size()==0){conditionVariable.wait(lock);}Tresult=dataQueue.front();dataQ

随机推荐