堆的 Shift Down 操作详解：从最大堆中取出元素

堆的 Shift Down 操作详解：从最大堆中取出元素

1. 堆的删除操作概述

在堆数据结构中，我们通常只能删除堆顶元素（最大堆中的最大值或最小堆中的最小值）。删除堆顶元素后，我们需要重新调整堆结构以维持堆的性质，这个过程称为'下沉'（Shift Down）操作。

2. Shift Down 操作原理

Shift Down 操作的基本步骤：

1. 将堆顶元素（最大值）取出
2. 将堆的最后一个元素移动到堆顶
3. 将这个新堆顶元素逐步向下比较和交换，直到找到合适的位置

Shift Down 过程图示

初始最大堆结构：

 62
/ \
52 30
/ \ / \
41 28 22 13
/ \
19 16

对应的数组表示：[null, 62, 52, 30, 41, 28, 22, 13, 19, 16]

第一步：取出堆顶元素 62

1. 交换堆顶 (62) 和最后一个元素 (16) 的位置：

 16
/ \
52 30
/ \ / \
41 28 22 13
/ \
19 62

数组状态：[null, 16, 52, 30, 41, 28, 22, 13, 19, 62]

2. 移除最后一个元素 (62)，count 减 1

第二步：开始 Shift Down 操作

1. 第一次比较：16 与其子节点 52 和 30 比较（52 > 30）

16 < 52，需要交换
 52
/ \
16 30
/ \ / \
41 28 22 13
/
19

数组状态：[null, 52, 16, 30, 41, 28, 22, 13, 19]

2. 第二次比较：16 的新位置，与其子节点 41 和 28 比较（41 > 28）

16 < 41，需要交换
 52
/ \
41 30
/ \ / \
16 28 22 13
/
19

数组状态：[null, 52, 41, 30, 16, 28, 22, 13, 19]

3. 第三次比较：16 的新位置，与其子节点 19 比较

16 > 19？不，16 < 19，需要交换
 52
/ \
41 30
/ \ / \
19 28 22 13
/
16

数组状态：[null, 52, 41, 30, 19, 28, 22, 13, 16]

4. 第四次比较：16 已经是叶子节点，Shift Down 结束

最终堆结构：

 52
/ \
41 30
/ \ / \
19 28 22 13
/
16

3. Java 实现代码

/**
 * 从最大堆中取出一个元素
 */
public class HeapShiftDown<T extends Comparable<T>> {
    protected T[] data;
      count;
      capacity;

    
      {
        
        data = (T[])  [capacity + ];
        count = ;
        .capacity = capacity;
    }

    
       {
         count;
    }

    
       {
         count == ;
    }

    
       {
         count +  <= capacity;
        data[count + ] = item;
        count++;
        shiftUp(count);
    }

    
     T  {
         count > ;
           data[]; 
        swap(, count); 
        count--; 
        shiftDown(); 
         ret;
    }

    
     T  {
         count > ;
         data[];
    }

    
       {
           data[i];
        data[i] = data[j];
        data[j] = t;
    }

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

    
       {
         ( * k <= count) { 
                * k; 
            
             (j +  <= count && data[j + ].compareTo(data[j]) > )
                j++; 
            
             (data[k].compareTo(data[j]) >= )
                ;
            swap(k, j); 
            k = j; 
        }
    }

    
        {
        HeapShiftDown<Integer> heap =  <Integer>();
           ; 
           ; 
        
         (   ; i < N; i++)
            heap.insert( (() (Math.random() * M)));
        Integer[] arr =  [N];
        
         (   ; i < N; i++) {
            arr[i] = heap.extractMax();
            System.out.print(arr[i] + );
        }
        
         (   ; i < N; i++)
             arr[i - ] >= arr[i];
    }
}