一种常见的数据结构，内部用二叉树的结构存储着数据，由于该二叉树满足完全二叉树的定义，所以我们可以通过数组来实现二叉树的存储。该数据结构满足堆首为堆中的最小元素，二叉树中的所有父节点都比子节点的要小。
首先要讨论的问题是构建堆
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;
			}
		}
	}
}

1、原理介绍：百度百科 

2、最小堆的构造和添加

#include <stdio.h>
#define N 9 // 最小堆得元素个数

int minHeap[N]; // 存放最小堆的数组
int index1 = 0; // 最小堆数组索引

void add(int d) // 向最小堆内添加数据
{
    if(index1 >= N)
    {
        printf("Out of range!\n");
        return;
    }
    int t = index1; // t指向存放位置
    int pt = (t - 1) / 2; // 父节点
    while(t > 0) // t指向0位置时结束循环
    {
        if(minHeap[pt] > d) // 当父节点数据比插入数据大时，将父节点数据下移
        {
            minHeap[t] = minHeap[pt];
            t = pt;
            pt = (t - 1) / 2;
        }
        else // 找到合适位置
            break;
    }
    minHeap[t] = d; // 最后存放数据位置
    index1++;
}
int main()
{
    int t[9] = {2, 1, 7, 3, 17, 19, 36, 25, 100};
    int i;
    for(i=0; i<9; i++)
    {
        add(t[i]);
    }

    for(i=0; i<9; i++) // 输出测试
    {
        printf("%d ", minHeap[i]);
    }
    printf("\n");
    return 0;
}

3、最小堆排序算法 

在构造最小堆时，没有必要一个节点一个节点的添加，可以将原来的数组看成一颗完全二叉树。并且知道数组元素个数。那么从最后一个非叶子节点的节点开始逐步向前，直到第一个节点。对每个节点与它的最小孩子节点比较，如果大于最小孩子节点，那么将孩子节点上移，该节点下移。直到找到不大于孩子节点的位置或者到孩子节点。将该节点值保存。 
排序思想： 

a. 使用变量index1=n-1。 

b. 数组长度为n，循环n-1次。 

c. 每次循环，构造(调整)一次最小堆，此时注意调整的数组长度为index1+1。排好序的元素不再调整。 

d. 交换第一个元素和第index1个元素，index1–。(较小元素放到后面) 

e. 直到循环结束，输出排序结果。

void outputt(int t[], int len) // 数组输出
{
    int i;
    for(i=0; i<len-1; i++) // 输出测试
    {
        printf("%d ", t[i]);
    }
    printf("%d\n", t[i]);
}

void heap(int t[], int len) // 调整二叉树生成堆
{
    int i;
    int l, r;
    int min, u;
    int ti, values;
    for(i=len/2-1; i>=0; i--) // 数组下标从0开始
    {
        ti = i; // 指向i元素存放位置
        values = t[i];
        while(ti < len)
        {
            l = 2 * ti + 1;
            r = l + 1;
            u = -1;

            if(l < len) // 取孩子中最小者最小
            {
                min = t[l];
                u = l;
            }
            if(r < len && t[r] < min)
            {
                min = t[r];
                u = r;
            }

            if(u == -1) // 到达叶子节点
                break;

            if(values > min)
            {
                t[ti] = min;
                ti = u;
            }
            else // 不大于孩子节点
                break;
        }
        t[ti] = values; // 存放该值
    }
}

void heapSort(int t[], int len) // 进行堆排序
{
    int tmp;
    int index1 = len - 1;
    while(index1 > 0) // 当未排序的只剩一个时，没必要再排
    {
        heap(t, index1 + 1); // 构造或调整最小堆
        tmp = t[0];
        t[0] = t[index1];
        t[index1] = tmp;
        outputt(t, 9); // 查看排序过程
        index1--;
    }
}

4、最小堆删除元素。每次删除第一个元素，并且把最后一个元素拿过来补充第一个元素，然后对这个新的二叉树进行调整使其满足最小堆的条件，不过此时调整仅从根节点调整即可。其实第三部分的堆排序中，只有第一次需要从最后一个非叶子节点进行调整，其他情况从根节点调整即可。最大堆的使用在最小堆的某些判断条件处更改即可。

目录

 

0.什么是堆

1.最大堆的实现

2.最小堆的实现

3.堆排序

0.什么是堆

小堆和大堆分为如下图： 




堆需要满足的条件：

1. 必须是二叉树，且必须是完全二叉树

2. 各个父节点必须大于或小于左右结点， 其中最顶层的根结点必须是最大或者最小的


堆可以使用list实现，就是按照层序遍历顺序将每个节点上的值存放在数组中。父节点和子节点之间存在如下的关系：

i 从0 开始

 parent = (i-1) // 2; left = 2*i + 1 ; right = 2*(i+1)

1.最大堆的实现


堆使用数组的形式表示，不需要使用指针


 




2. 在堆中增加元素





3,删除根节点，并重建堆结构




 

#最大堆的实现
class MaxHeap():
    def __init__(self, maxSize=None):
        self.maxSize = maxSize 
        self.li = [None] * maxSize
        self.count = 0
    
    def length(self):
        #求数组的长度
        return self.count 
    
    def show(self):
        if self.count <= 0:
            print('null')
        else:
            print(self.li[: self.count])
    
    def add(self, value):
        if self.count >= self.maxSize: #判断是否数组越界
            raise Exception('full')
        
        self.li[self.count] = value #将新节点增加到最后
        self._shift_up(self.count) # 递归构建大堆
        self.count += 1
    
    def _shift_up(self, index):
        #往大堆中添加元素，并保证根节点是最大的值:
        #1.增加新的值到最后一个结点，在add实现； 2.与父节点比较，如果比父节点值大，则交换
        if index > 0:
            parent = (index - 1) // 2 # 找到根节点
            if self.li[index] > self.li[parent]: #交换结点
                self.li[index], self.li[parent] = self.li[parent], self.li[index]
                self._shift_up(parent) #继续递归从底往上判断
            
    def extract(self):    
        #弹出最大堆的根节点，即最大值
        #1.删除根结点，将最后一个结点作为更结点 ； 2.判断根结点与左右结点的大小，交换左右结点较大的
        if not self.count:
            raise Exception('null')
        value = self.li[0] 
        self.count -= 1
        self.li[0] = self.li[self.count]  #将最后一个值变为第一个
        self._shift_down(0)
        return value
    
    def _shift_down(self, index):
        # 1.判断是否有左子节点并左大于根，左大于右；2.判断是否有右子节点，右大于根
        left = 2 * index +1
        right = 2 * index + 2
        largest = index 
        #判断条件
# 下面2个条件包含了，判断左右结点那个大的情况。如果为3， 4， 5,：
第一个判断条件使得largest=1，再执行第二个条件，则判断其左结点与右结点的大小
       if left < self.length() and self.li[left] > self.li[largest]:
            largest = left
        if right < self.length() and self.li[right] > self.li[largest]:
            largest = right

        if largest != index: # 将 两者交换
            self.li[index], self.li[largest] = self.li[largest], self.li[index]
            self._shift_down(largest)
        

m = MaxHeap(10)  
import numpy as np 
np.random.seed(123)
num = np.random.randint(100, size =10) #创建随机的10个数
print(m.length())
for i in num:
    m.add(i)
m.show()    
print(m.length())     
for i in range(5):
    print(m.extract(), end=' ,') 

 

2.最小堆的实现

#构造最小堆 
class MinHeap():
    def __init__(self, maxSize=None):
        self.maxSize = maxSize 
        self.array = [None] * maxSize 
        self._count = 0
    
    def length(self):
        return self._count 
    
    def show(self):
        if self._count <= 0:
            print('null')
        print(self.array[: self._count], end=', ')
    
    def add(self, value):
        #增加元素
        if self._count >= self.maxSize:
            raise Exception('The array is Full')
        self.array[self._count] = value
        self._shift_up(self._count)
        self._count += 1
    
    def _shift_up(self, index):
        #比较结点与根节点的大小， 较小的为根结点
        if index > 0:
            parent = (index - 1) // 2
            if self.array[parent] > self.array[index]:
                self.array[parent], self.array[index] = self.array[index], self.array[parent]
                self._shift_up(parent)
    
    def extract(self):           
        #获取最小值，并更新数组
        if self._count <= 0:
            raise Exception('The array is Empty')
        value = self.array[0]
        self._count -= 1 #更新数组的长度
        self.array[0] = self.array[self._count] #将最后一个结点放在前面
        self._shift_down(0)
        
        return value 
             
    def _shift_down(self, index):  
        #此时index 是根结点
        if index < self._count:
            left = 2 * index + 1
            right = 2 * index + 2
            #判断左右结点是否越界，是否小于根结点，如果是这交换
            if left < self._count and right < self._count and self.array[left] < self.array[index] and self.array[left] < self.array[right]:
                self.array[index], self.array[left] = self.array[left], self.array[index] #交换得到较小的值
                self._shift_down(left)
            elif left < self._count and right < self._count and self.array[right] < self.array[left] and self.array[right] < self.array[index]:
                self.array[right], self.array[index] = self.array[index], self.array[right]
                self._shift_down(right)
            
            #特殊情况： 如果只有做叶子结点
            if left < self._count and right > self._count and self.array[left] < self.array[index]:
                self.array[left], self.array[index] = self.array[index], self.array[left]
                self._shift_down(left)

mi = MinHeap(10)
print()
print('-------小顶堆----------')
for i in num:
    mi.add(i)
mi.show()
print(mi.length())
for _ in range(len(num)):
    print(mi.extract(), end=', ')
print()
print(mi.length())

参考：https://blog.csdn.net/qq_23869697/article/details/82735088

https://python-data-structures-and-algorithms.readthedocs.io/zh/latest/15_%E5%A0%86%E4%B8%8E%E5%A0%86%E6%8E%92%E5%BA%8F/heap_and_heapsort/#_4

 

3.堆排序

def maxHeapfy(alist, length, parent):
    left = 2 * parent + 1
    right = 2 * parent + 2
    largest = parent
    if left < length and alist[left] > alist[largest]:
        largest = left
    if right < length and alist[right] > alist[largest]:
        largest = right
    if largest != parent:
        alist[largest], alist[parent] = alist[parent], alist[largest]
        maxHeapfy(alist, length, largest)  # 递归构建

def buildMaxHeap(alist):  # 构建最大堆
    n = len(alist)
    lastParent = (n-1) // 2
    for i in range(lastParent, -1, -1):
        maxHeapfy(alist, n, i)

def heapSort(alist):
    buildMaxHeap(alist)
    n = len(alist)
    for i in range(n-1, -1, -1):
        alist[0], alist[i] = alist[i], alist[0]  # 将最大值放在最后面
        maxHeapfy(alist, i, 0)
    return alist

a = [30,50,57,77,62,78,94,80,84]
print(a)
print(heapSort(a))
alist = [2, 4, 1, 2, 5, 58, 45, 24, 67]
print(heapSort(alist))
b = [random.randint(1,1000) for i in range(1000)]
print(b)
print(heapSort(b))

 

项目推荐：

2000多G的计算机各行业电子资源分享（持续更新）

2020年微信小程序全栈项目之喵喵交友【附课件和源码】

Spring Boot开发小而美的个人博客【附课件和源码】

Java微服务实战296集大型视频-谷粒商城【附代码和课件】

Java开发微服务畅购商城实战【全357集大项目】-附代码和课件

最全最详细数据结构与算法视频-【附课件和源码】



 

//  对最小堆的各种操作
//  最小堆：完全二叉树，可以采用顺序存储结构

#include <iostream>
#include <stack>

const int DefaultSize = 100;

template <class T>
class MinHeap{
public:
    MinHeap(int sz = DefaultSize);
    MinHeap(T arr[], int n);
    ~MinHeap(){delete []heap;}
    bool Insert(const T &x); // 插入
    bool RemoveMin(); // 删除
    bool isEmpty()const; // 是否为空
    bool isFull()const; // 是否已满
    void PreOrder(); // 前序遍历完全二叉树
private:
    T *heap; // 动态数组存储最小堆
    int CurrentSize; // 目前最小堆的结点数
    void ShiftDown(int start, int m); // 下滑
    void ShiftUp(int start); // 上浮
};

// 构造函数
template <class T>
MinHeap<T>::MinHeap(int sz) {
    heap = new T[sz]; // 创建堆空间
    CurrentSize = 0;
}

// 构造函数
template <class T>
MinHeap<T>::MinHeap(T arr[], int n) {
    // 为什么求最后非叶要CurrentSize减去2，再除以2，而不是减去1，再除以2
    // 因为最后一个数组下标是CurrentSize-1，又因为：左结点j = 2 * i +
    //  1,知道j，想求i。可知是：i = (j - 1) / 2;所以，就出现了
    // CurrentPos = (CurrentSize - 2) / 2
    heap = new T[DefaultSize]; // 创建堆空间
    CurrentSize = n; // 当前堆大小
    for(int i = 0; i < n; i++)
        heap[i] = arr[i];
    int CurrentPos = (CurrentSize - 2) / 2; // 最后非叶
    while(CurrentPos >= 0) {
        // 从下到上逐渐扩大，形成堆
        ShiftDown(CurrentPos, CurrentSize-1);
        // 到CurrentSize-1为止
        CurrentPos--;
    }
}

// 向下调整
template <class T>
void MinHeap<T>::ShiftDown(int start, int m) {
    int i = start, j = 2 * i + 1; // j是i的左子女
    
    T temp = heap[i];
    while(j <= m) {
        if(j < m && heap[j] > heap[j+1])
            j++; // 选两个子女中较小者
        if(temp <= heap[j])
            break;
        else {
            heap[i] = heap[j];
            i = j;
            j = 2 * j + 1;
        }
    }
    heap[i] = temp;
}

// 向上调整
template <class T>
void MinHeap<T>::ShiftUp(int start) {
    // 从start开始，直到0或者当前值大于双亲结点的值时，调整堆
    int j = start, i = (j-1)/2; // i是j的双亲
    
    T temp = heap[j];
    while(j > 0) {
        if(heap[i] <= temp)
            break;
        else {
            heap[j] = heap[i];
            j = i;
            i = (j - 1) / 2;
        }
    }
    heap[j] = temp;
}

// 堆插入
template <class T>
bool MinHeap<T>::Insert(const T &x) {
    // 在堆中插入新元素x
    if(CurrentSize == DefaultSize) { // 堆满
        std::cout << "堆已满!\n";
        return false;
    }
    heap[CurrentSize] = x; // 插在表尾
    ShiftUp(CurrentSize); // 向上调整
    CurrentSize++;
    return true;
}

// 堆删除
template <class T>
bool MinHeap<T>::RemoveMin() {
    int x;
    
    if(!CurrentSize) {
        std::cout << "堆已空！\n";
        return false;
    }
    x = heap[0]; // 最小元素出列
    heap[0] = heap[CurrentSize-1]; // 用最后一个元素填补
    CurrentSize--;
    ShiftDown(0, CurrentSize-1); // 从0位置开始向下调整
    return true;
}

// 判断堆是否已空
template <class T>
bool MinHeap<T>::isEmpty()const {
    if(!CurrentSize)
        return true;
    return false;
}

// 判断堆是否已满
template <class T>
bool MinHeap<T>::isFull()const {
    if(CurrentSize == DefaultSize)
        return true;
    return false;
}

// 前序遍历
template <class T>
void MinHeap<T>::PreOrder() {
    std::stack<int> s;
    int i;
    
    i = 0;
    while(i < CurrentSize || !s.empty()) {
        while(i < CurrentSize) {
            std::cout << heap[i] << " ";
            s.push(i);
            i = 2 * i + 1;
        }
        if(!s.empty()) {
            i = s.top();
            s.pop();
            i = 2 * i + 2;
        }
    }
}

int main(int argc, const char * argv[]) {
    int finished, choose, x, len;
    int arr[] = {9, 17, 65, 23, 45, 78, 87, 53};
    
    len = sizeof(arr) / sizeof(arr[0]);
    finished = 0;
    MinHeap<int> h = MinHeap<int>(arr, len);
    
    while(!finished) {
        std::cout << "\n*************菜单*************\n";
        std::cout << "1:往最小堆中插入一个值：\n";
        std::cout << "2:删除最小堆中的最小值\n";
        std::cout << "3:判断最小堆是否为空\n";
        std::cout << "4:判断最小堆是否已满\n";
        std::cout << "5:前序遍历最小堆\n";
        std::cout << "6:退出\n";
        std::cout << "请输入你的选择[1-6]:";
        std::cin >> choose;
        switch(choose) {
            case 1:
                std::cout << "请输入要插入的值:";
                std::cin >> x;
                h.Insert(x);
                break;
            case 2:
                h.RemoveMin(); // 删除最小值
                break;
            case 3:
                if(h.isEmpty())
                    std::cout << "最小堆为空！\n";
                else
                    std::cout << "最小堆不为空！\n";
                break;
            case 4:
                if(h.isFull())
                    std::cout << "最小堆已满\n";
                else
                    std::cout << "最小堆还没满!\n";
                break;
            case 5:
                std::cout << "最小堆的数据为：\n";
                h.PreOrder();
                std::cout << std::endl;
                break;
            case 6:
                finished = 1;
                break;
            default:
                std::cout << "选择输入错误，请重新输入！\n";
        } // switch
    } // while
    return 0;
}