5.11. Heap shift down

发布时间 ： 2025-10-25 13:35:39 UTC      

Page Views: 49 views

This section describes how to take an element from the largest heap, called shift down, and only take out the element with the highest priority, that is, the root node. After taking out the original 62, here is how to fill the largest heap.

image0

In the first step, we put the last bit of the array to the root node, which does not satisfy the definition of the maximum heap.

image1

The adjustment process is to move the root node 16 down step by step, 16 is smaller than the child node, first compare which child node 52 and 30 is larger, and the large exchange position.

image2

Continue to compare the child nodes 28 and 41 of 16, so 16 and 41 swap positions.

image3

Continue to compare 16 with child node 15, 16, so there is no need to swap now, and finally our shift down operation is completed, maintaining a maximum heap property.

5.11.1. 4. Java instance code

源码包下载： Download

Src/runoob/heap/HeapShiftDown.java file code: 

package runoob.heap;
/*\*
 \* 往最大堆中取出一个元素
 */
public class HeapShiftDown {
    protected T[] data;
    protected int count;
    protected int capacity;
    // 构造函数, 构造一个空堆, 可容纳capacity个元素
    public HeapShiftDown(int capacity){
        //这里加1是指原来能装的元素个数，那去掉0位，只能装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);
    }
    // 从最大堆中取出堆顶元素, 即堆中所存储的最大数据
    public T extractMax(){
        assert count > 0;
        T ret = data[1];
        swap( 1 , count );
        count --;
        shiftDown(1);
        return ret;
    }
    // 获取最大堆中的堆顶元素
    public T getMax(){
        assert( count > 0 );
        return data[1];
    }
    // 交换堆中索引为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;
        }
    }
    //shiftDown操作
    private void shiftDown(int k){
        while( 2\*k <= count ){
            int j = 2\*k; // 在此轮循环中,data[k]和data[j]交换位置
            if( j+1 <= count && data[j+1].compareTo(data[j]) > 0 )
                j ++;
            // data[j] 是 data[2*k]和data[2*k+1]中的最大值
            if( data[k].compareTo(data[j]) >= 0 ) break;
            swap(k, j);
            k = j;
        }
        System.out.println("shiftDown结束");
    }
    // 测试 HeapShiftDown
    public static void main(String[] args) {
        HeapShiftDown heapShiftDown = new
HeapShiftDown(100);
        // 堆中元素个数
        int N = 100;
        // 堆中元素取值范围[0, M)
        int M = 100;
        for( int i = 0 ; i < N ; i ++ )
            heapShiftDown.insert( new Integer((int)(Math.random() \* M))
);
        Integer[] arr = new Integer[N];
        // 将最大堆中的数据逐渐使用extractMax取出来
        // 取出来的顺序应该是按照从大到小的顺序取出来的
        for( int i = 0 ; i < N ; i ++ ){
            arr[i] = heapShiftDown.extractMax();
            System.out.print(arr[i] + " ");
        }
        // 确保arr数组是从大到小排列的
        for( int i = 1 ; i < N ; i ++ )
            assert arr[i-1] >= arr[i];
    }
}
      
                    
                
                

                    

                        

                            
                                文章链接
                            
                            ：
                            5.11. Heap shift down 
                        

                    

                

            
        
        

            

    
        

            

                

                    
                        
                        
                            
Principles and Applications of WebGIS 

                        
                        
                             37
                        
                    
                    
                        

                            
 
 
 

                        

                    
                

                
            

        

    

    
        

            

                

                    
                        
                        
                            
Web框架 

                        
                        
                             942
                        
                    
                    
                        

                            
 
 
 

                        

                    
                

                
            

        

    

    
        

            

                

                    
                        
                        
                            
WEB基础 

                        
                        
                             287
                        
                    
                    
                        

                            
 
 
 

                        

                    
                

                
            

        

    

    
        

            

                

                    
                        
                        
                            
Principles, Technologies, and Methods of Geographic Information Systems 

                        
                        
                             102
                        
                    
                    
                        

                            
 
 
 In recent years, Geographic Information Systems (GIS) have undergone rapid development in both theoretical and practical dimensions. GIS has been widely applied for modeling and decision-making support across various fields such as urban management, regional planning, and environmental remediation, establishing geographic information as a vital component of the information era. The introduction of the “Digital Earth” concept has further accelerated the advancement of GIS, which serves as its technical foundation. Concurrently, scholars have been dedicated to theoretical research in areas like spatial cognition, spatial data uncertainty, and the formalization of spatial relationships. This reflects the dual nature of GIS as both an applied technology and an academic discipline, with the two aspects forming a mutually reinforcing cycle of progress.