import java.util.ArrayList;
import java.util.Arrays;
//必须传入一个Comparable的实现类，因为后续会用到类的内部比较器
public class Heap<E extends Comparable> {
    Comparable<? super E>[] list;//堆--存储Comparable的实现类
    int size;  //堆长度
    int capacity;//堆容量
    public Heap(int capacity){
        this.capacity=capacity;
        size=0;
        list=new Comparable[capacity+1];
    //初始化
    public void Init(E value,int index){
        if(index>0)
        { list[index]= value;
          size++;
            new RuntimeException("下标越界");
    //创建堆
    public void Build_Max_Heap(){
       for(int i=size/2;i>0;i--){
           int child=0;
           int parent = i;
           Comparable par_X= (E) list[i];
           for(;parent*2 <= size;parent=child){
               child=parent*2;
               if(child+1<=size && list[child].compareTo((E) list[child+1]) ==-1)
                   child++;
               if(par_X.compareTo((E) list[child])==1)
                   break;
               list[parent]=list[child];
           list[parent]=(E) par_X;
    //插入堆
   public void Insert(E node){
        list[++size]=node;
        for(int i=size;i/2>=0;i=i/2){
            if(i==1 || list[i/2].compareTo((E)node)==1){
                 list[i]=node;
                 break;
            else{
                list[i]=list[i/2];
   //删除堆
   public E Delete(){
        Comparable DeleteX=list[1];
        Comparable X=list[size--];
        int child=1;
        int parent=1;
        for(;parent*2<=size;parent=child){
            child=parent*2;
            if(child+1<=size && list[child].compareTo((E)list[child+1])==-1 )
                child++;
            if(X.compareTo((E)list[child])==-1)
                list[parent]=list[child];
                break;
        list[parent]=X;
        return (E)DeleteX;
    //测试数据
    public static void main(String[] args) {
        Heap<SSS> heap = new Heap<>(10);
        heap.Init(new SSS(1),1);
        heap.Init(new SSS(2),2);
        heap.Init(new SSS(3),3);
        heap.Init(new SSS(4),4);
        heap.Init(new SSS(5),5);
        heap.Insert(new SSS(6));
        heap.Build_Max_Heap();
        heap.Delete();
        for(int i=1;i<=heap.size;i++)
            System.out.println(heap.list[i]);
class SSS implements Comparable {
   int X;
    @Override
    public int compareTo(Object o) {
        SSS s2=(SSS) o;
        if(X>s2.X)
            return 1;
        if(X<s2.X)
            return -1;
        else return 0;
    public SSS(int X){
        this.X=X;
    @Override
    public String toString() {
        return "SSS{" +
                "X=" + X +
                '}';
                    创建堆的方式有两种，一种是一边插入结点，一边调用堆的插入方法调整堆，这样的时间复杂度就是O(NlogN)，而第二种方式就把时间复杂度缩减到了O(N)，它是采用先把结点插入好了，然后再来调整堆，并不是一边插入一边调整。但是从代码层面来看，可能会误以为第二种方式的时间复杂度也是O(NlogN)，但第二种方式是从下往上建立堆。举个例子，如下所示，假设堆中存在了N个节点(满足堆的性质)，采用第一种方式，再创建N个结点，那么插入第一个数时，就调用了时间复杂度为logN的插入方法，插入N个数后，时间复杂度为logN
				
堆排序（heapsort）是一种比较快速的排序方式，它的时间复杂度为O(nlgn)，并且堆排序具有空间原址性，任何时候只需要有限的空间来存储临时数据。我将用c++实现一个堆来简单分析一下。
堆排序的基本思想为：
1、升序排列，保持大堆；降序排列，保持小堆；
2、建立堆之后，将堆顶数据与堆中最后一个数据交换，堆大小减一，然后向下调整；直到堆中只剩下一个有效值；
下面我将简单分析一下：
第一步建立堆：
1、我用vector顺序表表示数组；
2、用仿函数实现大小堆随时切换，实现代码复用；
3、实现向下调整算法，时间复杂度为O（lgn）；
下面是我用某教材中的一个建最小堆的过程图，希望能更直观一些：
				
本来想写堆以及优先队列的，现在就只简单写写堆吧，先不写别的了，先把堆搞明白。
堆是什么
堆是一个 完全二叉树，每一个节点的值都必须 大于等于 或者 小于等于 其孩子节点的值。
堆的特点
插入 的时间复杂度：O(lgn)
删除 的时间复杂度：O(lgn)
获取最大值/最小值的 时间复杂度：O(1)
最大堆/最小堆
最大堆：每一个节点的值都必须 大于等于 其孩子节点的值。
最小堆：每一个节点的值都必须 小于等于 其孩子节点的值。
构建最大堆
构建最大堆的步骤分为一下几步：
把要插入的元素插入到堆中
				
现在常有两种建堆的方法，而这两种方法又有着不同的时间复杂度。下面分别陈述：
（1）自顶向下的建堆方式
这种建堆的方法具有O(n*log2n)的时间复杂度。从根结点开始，然后一个一个的把结点插入堆中。当把一个新的结点插入堆中时，需要对结点进行调整，以保证插入结点后的堆依然是大根堆。
其中h = log2(n+1)-1，第k层结点个数为2k个(当然最后一层结点个数可能小于2h)。第k层的一个结点插入之...
1）堆结构就是用数组实现的完全二叉树结构。（完全二叉树：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。）
2）完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
3）完全二叉树中如果每棵子树的最小值都在顶部就是小根堆
4）堆结构的heapInsert（插入）与heapify（调整）操作
5）堆结构的增大和减少
6）优先级队列结构，就是堆结构
语言提供的堆结构 vs 手写的堆结构
取决于我们有没有动态改信息的需求。
语言提供的堆结构，如果你动态改数据，不保证依然有序
[ 手写堆 
3、左右节点的值都比当前节点的大
从定义可知，根节点是树中的最小值，
最小堆一般用链表存储，父子节点的关系，用纯数学的关系表示为：假设当前节点的在链表中的索引为n,左子节点为2n+1 ,右子节点为2n+2
void swap(int *a, int *b);
void adjustHeap(int param1,int j, int inNums[]);
void  HeapSort(int nums, int inNums[]);
//大根堆进行调整
void adjustHeap(int param1, int j, i
				
数据结构是计算机科学中研究数据组织、存储、管理和访问的一门学科，是计算机科学的核心内容之一。数据结构包括线性结构、树结构、图结构等，其选择取决于数据的组织和使用方式。数据结构的设计需要考虑效率、存储空间、操作的复杂度等因素。
在数据结构中，常用的算法包括：查找算法、排序算法、图算法等。其中，查找算法主要用于在给定的数据结构中查找特定的数据元素；排序算法则用于对数据元素进行排序；图算法则用于解决图结构中的问题，如最短路径、最小生成树等。
常见的数据结构包括：数组、链表、栈、队列、树、堆、散列表、图等。不同的数据结构适用于不同的场景，需要根据具体的应用场景选择合适的数据结构。例如，数组适用于数据元素数量固定的情况，而链表适用于数据元素数量不固定的情况。栈和队列则适用于需要先进先出或后进先出的场景，而树和图则适用于更复杂的数据结构和问题。