创建堆的方式有两种，一种是一边插入结点，一边调用堆的插入方法调整堆，这样的时间复杂度就是
 O(NlogN)，而第二种方式就把时间复杂度缩减到了O(N)，它是采用先把结点插入好了，然后再来调整堆，并不是一边插入一边调整。
 但是从代码层面来看，可能会误以为第二种方式的时间复杂度也是O(NlogN)，但第二种方式是从下往上建立堆。举个例子，如下所示，假设堆中存在了N个节点(满足堆的性质)，采用第一种方式，再创建N个结点，那么插入第一个数时，就调用了时间复杂度为logN的插入方法，插入N个数后，时间复杂度为logN。
 
 
让我们看看第二种方式会如何？
 先把N个结点创建到树中，把这N个结点具体化，我们看到在调整树时，第一次是以倒数第二层的结点作为根节点，然后来调整这棵子树，也就是它的时间复杂度不再是logN了，因为远远没到N个结点，远远没到整颗树的高度，它的时间复杂度应该如下判断，在最坏情况下，树中每个结点，会一直向下查找，一直到底，假设树高为h,则倒数第二层会向下查找1次，倒数第三层会向下查找2次…
 倒数第二层结点数为2(h-2),倒数第三层2h-3…
 
 
 
JAVA代码实现
 
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++;
        }
        else
            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];
            else
                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 +
                '}';
    }
}

 
目录：
 
1.堆
2.堆的实现
2.1堆的向下调整算法(建小堆)
2.2 堆向下调整算法(建小堆)实现
2.3 堆的向上调整算法
2.4 向上调整算法(建小堆)实现
2.5 数组建堆算法(建小堆)
2.6 数组建堆算法(建小堆)实现
2.7 堆排序(降序)
2.8 堆排序(降序)实现
2.9 建堆的时间复杂度
 

 
1.堆
 
大根堆：所有父节点大于等于孩子节点
 
 
小根堆：所有父节点小于等于孩子节点
 
 堆的性质：
 
• 堆中某个节点的值总是不大于或不小于其父节点的值
 
• 堆总是一棵完全二叉树
 
2.堆的实现
 
堆的实现请点击—> 堆的实现
 
现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。
 int a[] = {27,15,19,18,28,34,65,49,25,37};
 
2.1堆的向下调整算法(建小堆)
 
向下调整算法-前提：当前树的左右子树必须都是一个小堆
 向下调整算法的核心思想：选出左右孩子中小的哪一个，跟父亲交换，小的往上浮，大的往下沉，如果要建大堆则相反
 
如下图所示为一个向下调整法调小堆
 
 
2.2 堆向下调整算法(建小堆)实现
 
//堆向下调整算法
//建小堆
void AdjustDown(int* a, int n, int root)
{
	int parent = root;
	int child = parent * 2 + 1;
	//孩子超过数组下标结束
	while (child < n)
	{
		//child始终左右孩子中小的那个
		if (a[child + 1] < a[child] && child + 1 <n)//防止没有右孩子
		{
			++child;
		}
		//小的往上浮，大的往下浮
		if (a[child] < a[parent])
		{
			int tem = a[parent];
			a[parent] = a[child];
			a[child] = tem;
			parent = child;
			child = parent * 2 + 1;
		}
		//中途child>parent则已满足小堆，直接break
		else
		{
			break;
		}
	}
}
 
2.3 堆的向上调整算法
 
使用场景：向堆中插入数据，需要使用向上调整算法调整，因为向堆中插入数据是将数据插入到下标为size的位置，此时就不满足小堆(大堆)，因此，需要堆其进行调整，向上调整算法和向下调整算法思路类似，此处以小堆为例，向上调整法只需从插入的节点位置开始和父节点比较，若a[chaild]<a[parent],则交换，若a[chaild]>=a[parent]则说明越界满足小堆，直接break
 
如下图所示插入一个数据使用向上调整法调整
 
 
2.4 向上调整算法(建小堆)实现
 
//堆的向上调整算法
//建小堆
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			int tem = a[parent];
			a[parent] = a[child];
			a[child] = tem;
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
 
2.5 数组建堆算法(建小堆)
 
若左右子树不是小堆——想办法把左右子树处理成小堆
 可以从倒数第一个非叶子节点的位置开始向下调整
 
如下图所示可以按图中的步骤依次向下调整
 最后一个非叶子节点的下标为 (n-1-1)/2
 
 
2.6 数组建堆算法(建小堆)实现
 
	int n = sizeof(a) / sizeof(int);
	//数组建堆算法
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(arr, n, i);
	}
 
2.7 堆排序(降序)
 
下面我们将上面建好的小堆进行降序排序
 
堆排序(降序)的核心思想：因为建小堆可以选出最小的数即根节点，我们将每次建好的小堆的最后一个叶子节点和根节点进行交换，交换后不把最后一个数看作堆里的数据，此时根的左右子树依旧是大堆，然后我们再用向下调整算法选出次小的如此循环直到堆里剩一个数结束
 
• 升序建大堆
 • 降序建小堆
 
2.8 堆排序(降序)实现
 
//降序
void HeapSort(int* a, int n)
{
	//建小堆
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	//把最小的换到最后一个位置，不把最后一个数看作堆里的
	//每次选出剩下数中最小的
	//从后往前放
	while (end > 0)
	{
		int tem = a[end];
		a[end] = a[0];
		a[0] = tem;
		//选出次小的数
		AdjustDown(a, end, 0);
		--end;
	}
}
 
2.9 建堆的时间复杂度
 
最坏的情况及满二叉树，且每个节点都需要调整
 
 由以上推论过程可得建堆的时间复杂度为O(N);
 向下调整算法的时间复杂度为O(log2N);
 所以堆排序的时间复杂度为O(N*log2N);

一种常见的数据结构，内部用二叉树的结构存储着数据，由于该二叉树满足完全二叉树的定义，所以我们可以通过数组来实现二叉树的存储。该数据结构满足堆首为堆中的最小元素，二叉树中的所有父节点都比子节点的要小。
 
首先要讨论的问题是构建堆
 
1从0开始构建，直接一项一项的添加进堆
 
这是一个动态添加的过程，每次添加都假设现在的堆满足最大堆的定义，每次添加一项我们就需要把它放到合适的位置。一个很初始的想法就是把节点放在完全二叉树的下一个节点上，如果不满足最小堆的定义再调整，此时我们发现冲突点转移到了高度为1层的节点上，那么我们把新添加的节点与父节点比较，如果存在冲突，我们就交换两者位置，此时高度为0与1层的节点之间的关系满足了最小堆定义，此时矛盾转义到了高度为2层的节点上，重复之前的操作，此时我们会发现高度为0,1,2的层满足最小堆的定义，依次我们可以推到树的根节点。  
 

 
 
2从一个已有数组开始构建
 
这里也可以通过动态构建，假设目前数组可以构成一个高度为h的二叉树，我们可以通过从高度为1的最小堆开始构建，然后利用高度为1的最小堆构建高度为2的最小堆，一直到高度为h的最小堆，这个过程中每个分析单元 我们只需要考虑将堆的根节点放到合适的位置，这样新构造的堆肯定能满足最小堆的要求。
 

 
 
其次要考虑的问题是取元素的过程
 
我们需要拿出去的元素肯定是堆首，但是当我们拿出堆首之后，这个堆就存在着一个空槽，我们的问题是怎么填补这个空槽，我一个直接的想法是取子节点中最小的元素来填补空槽，那么空槽就会被推到下一层，但是存在着一个问题，当我们把空槽推到最底层的时候我们要选择哪个元素去填补这个空槽，由于需要满足完全二叉树，那么我们很自然的想到拿出最后一个元素填充这个空槽，但是注意这样填补了可能导致整个堆不满足最小堆的定于，我们需要处理这个元素比父元素大的情况，使他一路上浮到该有的位置，
 
这个过程其实是和直接拿最后的元素填充到堆首并且将该元素推到该有的位置是等价的。
 

 
 
另外需要考虑的就是关于最小堆的一些有意义的操作了，其中一个就是实现优先队列，普通的进队出队操作和最小堆的进堆出堆操作是一致的，剩下需要考虑的就是提高和降低优先级的操作，这个在最小堆中实现也很简单，只是降低或增加排序键值的值，我们可以通过一次线性搜索找到需要操作的对象，然后通过一次堆排序来实现
 

 
 
对于最小堆来说  进堆操作和出堆操作的时间复杂度都是O（log（n）），也就是元素需要上浮或者下潜log（n）层，但是构建一个最小堆的过程时间复杂度为O（n）  总的来说效率还是很高的
 

 
 

package 最小堆;

public class MinHeap {

	public static void main(String[] args) {
		MinHeap minHeap = new MinHeap(7);
		int[] array = { 4, 3, 2, 1, 5, 7 };
		int k = 6;
		minHeap.buildup(array, k);
		minHeap.addElement(6);
		minHeap.increasePriority(6, 10);
		minHeap.decreasePriority(2, 8);
		minHeap.deleteInnode(3);
		while(minHeap.hasMore()){
			System.out.println(minHeap.pushoutHeapHead());
		}
	}

	int[] heap; // 0号位弃用 来实现二叉树到数组的映射
	int heapSize; // 记录堆的大小
	private int MaxSize; // 记录堆的最大大小

	public MinHeap(int defaultSize) {
		heap = new int[defaultSize + 1];
		heapSize = 0;
		MaxSize = defaultSize;
	}

	// 把元素向上推到合适位置
	private void pushUp(int index) {
		while (index > 1) {
			if (heap[index] < heap[index >> 1]) {
				int temp = heap[index];
				heap[index] = heap[index >> 1];
				heap[index >> 1] = temp;
				index = index >> 1;
			} else {
				return;
			}
		}
	}

	// 把元素向下推到合适的位置
	private void pollDown(int index) {
		int OrNum = -1;
		if ((index << 1) <= heapSize && heap[index] > heap[index << 1]) {
			OrNum = 0;
		}

		if ((index << 1 | 1) <= heapSize && heap[index] > heap[index << 1 | 1]) {
			if (OrNum > -1 && heap[index << 1] < heap[index << 1 | 1]) {

			} else {
				OrNum = 1;
			}
		}
		if (OrNum >= 0) {
			int temp = heap[index];
			heap[index] = heap[index << 1 | OrNum];
			heap[index << 1 | OrNum] = temp;
			pollDown(index << 1 | OrNum);
		} else {
			return;
		}
	}

	// 传入参数K表示 数组的前k个初始化成堆，另外要求k要小于堆的最大大小
	// 结果为 最后类中存在着一个大小为K的堆
	public void buildup(int[] inputArray, int k) {
		for (int i = 0; i < k; i++) {
			heap[i + 1] = inputArray[i];
		}
		heapSize = k;
		int index = Integer.highestOneBit(k) - 1;
		while (index > 0) {
			pollDown(index);
			index--;
		}
	}

	// 向堆中添加元素
	public void addElement(int inNum) {
		heapSize++;
		heap[heapSize] = inNum;
		pushUp(heapSize);
	}

	// 将堆首推出堆
	public int pushoutHeapHead() {
		int reVal = heap[1];
		heap[1] = heap[heapSize];
		heapSize--;
		pollDown(1);
		return reVal;
	}

	// 辅助取出堆首
	public boolean hasMore() {
		return heapSize > 0;
	}

	// 这个方法是通过key 找到节点，将该节点的优先级降低
	// 由于目前实现中的key和优先级一致可能不明显，但是可以用这样的结构实现任务调度
	public void decreasePriority(int key, int value) {
		for (int i = 1; i <= heapSize; i++) {
			if (heap[i] == key) {
				heap[i] += value;
				pollDown(i);
				return;
			}
		}
	}

	public void increasePriority(int key, int value) {
		for (int i = 1; i <= heapSize; i++) {
			if (heap[i] == key) {
				heap[i] -= value;
				pushUp(i);
				return;
			}
		}
	}

	public void deleteInnode(int key) {
		for (int i = 1; i <= heapSize; i++) {
			if (heap[i] == key) {
				heap[i] = heap[heapSize];
				heapSize--;
				pollDown(i);
				return;
			}
		}
	}
}


 

 

Floyd建堆算法（自下而上下滤）建立规模为n的完全二叉堆的时间复杂度为：O(n)
 
一般的暴力建堆算法（自上而下上滤）时间复杂度为：O（nlogn）