数据结构之堆（Heap）-蒲公英云

数据结构之堆（Heap）

青旅半醒 2024-04-17 19:40 162阅读 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的头。
在这里插入图片描述

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]+" ");
        }
    }
}