数据结构之堆（Heap）

青旅半醒 2024-04-17 19:40 15阅读 0赞

堆是由完全二叉树实现的  
**完全二叉树：** 若设二叉树的深度为h，除第h层外，其他各层（1—h-1）的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。

left_son_id = father_id*2+1
    
    right_son_id = father_id*2+2

**最大堆：** 每个结点的键值（key）都大于等于子节点键值，最大堆的最大元素在根节点，位于array的头。  
**最小堆：** 每个结点的键值（key）都小于等于子节点键值，最小堆的最小元素在根节点，位于array的头。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BlcmZlY3RtYXRjaF9H_size_16_color_FFFFFF_t_70]

public class Heap { 
        //parent = (child-1)/2
        //c1 = 2p+1
        //c2 = 2p+2
    
        //n表示这个树有多少个节点
        //i表示要对哪个节点进行堆化
        public static void heapify(int[] tree,int n,int i){ 
            if (i>=n){ 
                return;
            }
            int c1 = 2*i+1;
            int c2 = 2*i+2;
            int max = i;
            if (c1<n && tree[c1] > tree[max]){ 
                max = c1;
            }if (c2<n && tree[c2] > tree[max]){ 
                max = c2;
            }if (max != i){ 
                swap(tree,max,i);
                heapify(tree,n,max);
            }
        }
    
        public static void swap(int[] arr,int i,int j){ 
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    
        //建堆
        public static void build_Heap(int[] tree,int n){ 
            int last_node = n-1;
            int parent = (last_node-1)/2;
            for (int i=parent;i>=0;i--){ 
                heapify(tree,n,i);
            }
        }
    
        //堆排序
        public static void heap_sort(int[] tree,int n){ 
            build_Heap(tree,n);
            for(int i=n-1;i>=0;i--){ 
                swap(tree,i,0);//最后一个节点与第一个节点交换
                heapify(tree,i,0);
            }
        }
        public static void main(String[] args) { 
            int[] a = { 2,5,3,1,10,4};
            heap_sort(a,6);
            for (int i=0;i<6;i++){ 
                System.out.print(a[i]+" ");
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BlcmZlY3RtYXRjaF9H_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/376059e9f7ae42ff85624dc1bda2d207.jpg