目录

堆（Heap）

堆的基本接口设计

二叉堆（Binary Heap）

获取最大值

最大堆 - 添加

添加过程总结

最大堆 — 添加优化

最大堆 - 删除

replace（替换堆顶的元素）

最大堆 — 批量建堆（Heapify）

自上而下的上滤

自下而上的下滤

效率对比

二叉堆源码

堆的基本接口 Heap.java

抽象类 AbstractHeap.java

二叉堆 BinaryHeap.java

构建一个最小堆

TOP K 问题

【引出堆】

• 堆   获取最大值：O(1)、删除最大值：O(logn)、添加元素：O(logn)
   

【Top K问题】

• 什么是TopK问题
  • 从海量数据中找出前K个数据
• 比如
  • 从100万个整数中找出最大的100个整数
• TopK问题的解法之一：可以用数据结构“堆”来解决

堆（Heap）

堆（Heap）是一种 树状 的数据结构，常见的堆实现有

• 二叉堆（Binary Heap，完全二叉堆）
• 多叉堆（D-heap、D-ary Heap）
• 索引堆（Index Heap）
• 二项堆（Binomial Heap）
• 斐波那契堆（Fibonacci Heap）
• 左倾堆（Leftist Heap，左式堆）
• 斜堆（Skew Heap）
• 堆的重要性质：任意节点的值总是 ≥（ ⩽） 子节点的值
  • 如果任意节点的值总是 ≥ 子节点的值，称为：最大堆、大根堆、大顶堆
  • 如果任意节点的值总是 ⩽ 子节点的值，称为：最小堆、小根堆、小顶堆
• 堆中的元素必须具备可比较性（跟二叉搜索树一样）

堆的基本接口设计

二叉堆（Binary Heap）

• 二叉堆的逻辑结构就是一棵完全二叉树，所以也叫完全二叉堆
• 鉴于完全二叉树的一些特性，二叉堆的底层（物理结构）一般用数组实现即可

• 使用数组存放

【索引 i 的规律（n 是元素数量）】

获取最大值

• 注意检测数组不能为空

public E get() {
	emptyCheck();
	return elements[0];
}
private void emptyCheck() {
	if (size == 0) {
		throw new IndexOutOfBoundsException("Heap is empty");
	}
}

最大堆 - 添加

• 添加一个新元素80

• 和父节点进行交换

• 进行循环比较，交换

添加过程总结

• 代码实现

/**
 * 最大堆 — 添加
 */
public void add(E element) {
	// 检测传入的元素非空
	elementNotNullCheck(element);
	// 扩容操作，确保容量大于当前元素个数大小
	ensureCapacity(size + 1);
	// 将要添加的元素放到数组最后
	elements[size++] = element;
	// 上滤操作
	siftUp(size - 1);
}
/**
 * 让index位置的元素上滤
 */
private void siftUp(int index) {
	E e = elements[index]; // 要添加的节点
	while (index > 0) { // 直到比较到根结点
		int pindex = (index - 1) >> 1; // 父节点索引
		E p = elements[pindex]; // 添加节点的父节点
		if (compare(e, p) <= 0) return;
		
		// 交换index、pindex位置的内容
		E tmp = elements[index];
		elements[index] = elements[pindex];
		elements[pindex] = tmp;
		
		// 重新赋值index
		index = pindex;
	}
}

最大堆 — 添加优化

/**
 * 让index位置的元素上滤
 */
private void siftUp(int index) {
	E element = elements[index];
	while (index > 0) {
		// 父节点索引 = (子节点索引-1) / 2
		int parentIndex = (index - 1) >> 1;
		E parent = elements[parentIndex];
		if (compare(element, parent) <= 0) break;
		
		// 将父元素存储在index位置
		elements[index] = parent;
		
		// 重新赋值index
		index = parentIndex;
	}
	elements[index] = element;
}

最大堆 - 删除

/**
 * 最大堆—删除堆顶元素
 */
public E remove() {
	// 检测数组不能为空
	emptyCheck(); 
	// 获取数组最后元素的索引
	int lastIndex = --size;
	// 获取要删除元素的节点
	E root = elements[0];
	elements[0] = elements[lastIndex];
	elements[lastIndex] = null;
	
	siftDown(0); // 下滤操作
	return root;
}
/**
 * 让index位置的元素下滤
 */
private void siftDown(int index) {
	E element = elements[index];
	int half = size >> 1; // 非叶子节点的数量
	// 第一个叶子节点的索引 == 非叶子节点的数量
	// index < 第一个叶子节点的索引
	// 必须保证index位置是非叶子节点
	while (index < half) { 
		// index的节点有2种情况
		// 1.只有左子节点
		// 2.同时有左右子节点
		
		// 默认为左子节点跟它进行比较
		int childIndex = (index << 1) + 1;
		E child = elements[childIndex];
		
		// 右子节点
		int rightIndex = childIndex + 1;
		
		// 选出左右子节点最大的那个
		if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
			child = elements[childIndex = rightIndex];
		}
		
		if (compare(element, child) >= 0) break;

		// 将子节点存放到index位置
		elements[index] = child;
		// 重新设置index
		index = childIndex;
	}
	elements[index] = element;
}

replace（替换堆顶的元素）

public E replace(E element) {
	elementNotNullCheck(element);
	
	E root = null;
	if (size == 0) {
		elements[0] = element;
		size++;
	} else {
		root = elements[0];
		elements[0] = element;
		siftDown(0);
	}
	return root;
}

最大堆 — 批量建堆（Heapify）

• 自上而下的上滤
• 自下而上的下滤

自上而下的上滤

自下而上的下滤

效率对比

• 自上而下的上滤时间复杂度：O ( n l o g n ) O(nlogn)O(nlogn)
• 自下而上的下滤时间复杂度：O ( n l o g k ) O(nlogk)O(nlogk)

二叉堆源码

堆的基本接口 Heap.java

public interface Heap<E> {
	int size();	// 元素的数量
	boolean isEmpty();	// 是否为空
	void clear();	// 清空
	void add(E element);	 // 添加元素
	E get();	// 获得堆顶元素
	E remove(); // 删除堆顶元素
	E replace(E element); // 删除堆顶元素的同时插入一个新元素
}

抽象类 AbstractHeap.java

@SuppressWarnings("unchecked")
public abstract class AbstractHeap<E> implements Heap<E> {
	protected int size;
	protected Comparator<E> comparator;
	
	public AbstractHeap(Comparator<E> comparator) {
		this.comparator = comparator;
	}
	
	public AbstractHeap() {
		this(null);
	}
	
	@Override
	public int size() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return size == 0;
	}
	
	protected int compare(E e1, E e2) {
		return comparator != null ? comparator.compare(e1, e2) 
				: ((Comparable<E>)e1).compareTo(e2);
	}
}

二叉堆 BinaryHeap.java

/**
 * 二叉堆（最大堆）
 */
@SuppressWarnings("unchecked")
public class BinaryHeap<E> extends AbstractHeap<E> {
	private E[] elements;
	private static final int DEFAULT_CAPACITY = 10;
	
	public BinaryHeap(E[] elements, Comparator<E> comparator)  {
		super(comparator);
		
		if (elements == null || elements.length == 0) {
			this.elements = (E[]) new Object[DEFAULT_CAPACITY];
		} else {
			size = elements.length;
			int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
			this.elements = (E[]) new Object[capacity];
			for (int i = 0; i < elements.length; i++) {
				this.elements[i] = elements[i];
			}
			heapify();
		}
	}
	
	public BinaryHeap(E[] elements)  {
		this(elements, null);
	}
	
	public BinaryHeap(Comparator<E> comparator) {
		this(null, comparator);
	}
	
	public BinaryHeap() {
		this(null, null);
	}

	@Override
	public void clear() {
		for (int i = 0; i < size; i++) {
			elements[i] = null;
		}
		size = 0;
	}

	@Override
	public void add(E element) {
		elementNotNullCheck(element);
		ensureCapacity(size + 1);
		elements[size++] = element;
		siftUp(size - 1);
	}

	@Override
	public E get() {
		emptyCheck();
		return elements[0];
	}

	/**
	 * 删除堆顶元素
	 */
	public E remove() {
		emptyCheck();
		
		int lastIndex = --size;
		E root = elements[0];
		elements[0] = elements[lastIndex];
		elements[lastIndex] = null;
		
		siftDown(0);
		return root;
	}

	@Override
	public E replace(E element) {
		elementNotNullCheck(element);
		
		E root = null;
		if (size == 0) {
			elements[0] = element;
			size++;
		} else {
			root = elements[0];
			elements[0] = element;
			siftDown(0);
		}
		return root;
	}
	
	/**
	 * 批量建堆
	 */
	private void heapify() {
		// 自上而下的上滤
//		for (int i = 1; i < size; i++) {
//			siftUp(i);
//		}
		
		// 自下而上的下滤
		for (int i = (size >> 1) - 1; i >= 0; i--) {
			siftDown(i);
		}
	}
	
	/**
	 * 让index位置的元素下滤
	 * @param index
	 */
	private void siftDown(int index) {
		E element = elements[index];
		int half = size >> 1; // 非叶子节点的数量
		// 第一个叶子节点的索引 == 非叶子节点的数量
		// index < 第一个叶子节点的索引
		// 必须保证index位置是非叶子节点
		while (index < half) { 
			// index的节点有2种情况
			// 1.只有左子节点
			// 2.同时有左右子节点
			
			// 默认为左子节点跟它进行比较
			int childIndex = (index << 1) + 1;
			E child = elements[childIndex];
			
			// 右子节点
			int rightIndex = childIndex + 1;
			
			// 选出左右子节点最大的那个
			if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
				child = elements[childIndex = rightIndex];
			}
			
			if (compare(element, child) >= 0) break;

			// 将子节点存放到index位置
			elements[index] = child;
			// 重新设置index
			index = childIndex;
		}
		elements[index] = element;
	}
	
	/**
	 * 让index位置的元素上滤
	 */
	private void siftUp(int index) {
//		E e = elements[index];
//		while (index > 0) {
//			int pindex = (index - 1) >> 1;
//			E p = elements[pindex];
//			if (compare(e, p) <= 0) return;
//			
//			// 交换index、pindex位置的内容
//			E tmp = elements[index];
//			elements[index] = elements[pindex];
//			elements[pindex] = tmp;
//			
//			// 重新赋值index
//			index = pindex;
//		}
		E element = elements[index];
		while (index > 0) {
			// 父节点索引 = (子节点索引-1) / 2
			int parentIndex = (index - 1) >> 1;
			E parent = elements[parentIndex];
			if (compare(element, parent) <= 0) break;
			
			// 将父元素存储在index位置
			elements[index] = parent;
			
			// 重新赋值index
			index = parentIndex;
		}
		elements[index] = element;
	}
	
	private void ensureCapacity(int capacity) {
		int oldCapacity = elements.length;
		if (oldCapacity >= capacity) return;
		
		// 新容量为旧容量的1.5倍
		int newCapacity = oldCapacity + (oldCapacity >> 1);
		E[] newElements = (E[]) new Object[newCapacity];
		for (int i = 0; i < size; i++) {
			newElements[i] = elements[i];
		}
		elements = newElements;
	}
	
	private void emptyCheck() {
		if (size == 0) {
			throw new IndexOutOfBoundsException("Heap is empty");
		}
	}
	
	private void elementNotNullCheck(E element) {
		if (element == null) {
			throw new IllegalArgumentException("element must not be null");
		}
	}
}

构建一个最小堆

• 在写完最大堆以后，实现最小堆不需要修改源代码，只需要在创建堆时，传入与最大堆比较方式相反的比较器即可。

public static void main(String[] args) {
	Integer[] data = {88, 44, 53, 41, 16, 6, 70, 18, 85, 98, 81, 23, 36, 43, 37};
	BinaryHeap<Integer> heap = new BinaryHeap<>(data, new Comparator<Integer>() {
		public int compare(Integer o1, Integer o2) {
			return o2 - o1; // 与最大堆比较方式相反
		}
	});
}

TOP K 问题

public static void main(String[] args) {
	// 新建一个小顶堆
	BinaryHeap<Integer> heap = new BinaryHeap<>(new Comparator<Integer>() {
		public int compare(Integer o1, Integer o2) {
			return o2 - o1;
		}
	});
	
	// 找出最大的前k个数
	int k = 3;
	Integer[] data = {51, 30, 39, 92, 74, 25, 16, 93, 
			91, 19, 54, 47, 73, 62, 76, 63, 35, 18, 
			90, 6, 65, 49, 3, 26, 61, 21, 48};
	for (int i = 0; i < data.length; i++) {
		if (heap.size() < k) { // 前k个数添加到小顶堆
			heap.add(data[i]); // logk
		} else if (data[i] > heap.get()) { // 如果是第 k + 1 个数，并且大于堆顶元素
			heap.replace(data[i]); // logk
		}
	}
	// O(nlogk)
}

• 如果是找出最小的前 k 个数呢？
  • 用大顶堆
  • 如果小于堆顶元素，就使用 replace 操作。

本文欢迎转载，转载前请联系作者。若未经允许转载，转载时请注明出处，谢谢！ http://blog.csdn.net/colton_null 作者：喝酒不骑马 Colton_Null from CSDN

一.什么是二叉堆？

二叉堆(binary heap)是一种通常用于实现优先队列的数据结构。要想知道二叉堆是什么东西，得从两方面介绍它：结构性和堆序性。

1.结构性

二叉堆是一颗除底层外被完全填满的二叉树，对于底层上的元素满足从左到右填入的特性。如下图所示。

所以，鉴于二叉堆的这个结构特性，我们可以很容易得出——一颗高为h的二叉堆有$2^h$到$2^{h+1}-1$ 个节点。

而且，基于二叉堆的这个特性，我们可以用一个数组在表示这种数据结构，不需要使用链。如下图所示。

数组上任意位置i上的元素，它的左节点在2i上，右节点在2i + 1上，它的父节点在└i/2┘。不用链表的好处在于，这么做对于计算机来说，访问某一元素的效率很高，不需要遍历即可访问。

2.堆序性

这里我们用最小堆(min-heap)来说明。

在堆中，每个节点n，都小于或等于它的两个子节点。如下图所示。

当然，我们可以类比处最大堆(max-heap)即每个节点都大于或等于它的子节点。

根据二叉堆的这个性质，最小元素或者最大元素即为根节点。我们直接就可以访问到这个最小的元素，即array[1]（数组结构参考结构性）。

二.保持二叉堆的特性

在使用二叉堆的时候，我们对二叉堆插入和获取最小值的操作，会破坏二叉堆的特性。那么我们需要在每次操作之后，对二叉堆进行维护。

1.上滤

我们在执行插入(insert)操作的时候，可以采用上滤(percolate up)策略对二叉树进行维护。

首先在插入元素t时，在底层创建一个空穴，以保证完全二叉树的性质。如果元素t可以直接放在该空穴中不影响堆的堆序性，则插入完成；如果元素t不能直接放置在空穴中（即对于min-heap来说，t小于它的根节点或对于max-heap来说，t大于它的根节点），则把空穴的根节点放置在空穴中，原根节点被视为空穴。直到t被放入在合适的空穴中。

过程如下图所示，插入元素18。

2.下滤

在我们获取最小元素（即获取根节点并删除它时），我们需要用下滤(percolate down)策略来维护堆序性。

当删除最小元素时，根节点变为空穴，那么为了保证二叉堆的结构性，所以要把最后一个元素x移动到该堆的某个地方。如果x可以直接放入到空穴中，则下滤结束；否则，空穴子节点中最小或最大的值（这要看是min-heap还是max-heap，min-heap为最小值，max-heap为最大值）放入到空穴中，然后空穴下移一位，直到x可以被放置在空穴中。

过程如下图所示。

3.最小二叉堆的Java实现

BinaryHeap.java

public class BinaryHeap<T extends Comparable<? super T>> {
    public BinaryHeap() {
        this(DEFAULT_CAPACITY);
    }

    public BinaryHeap(int capacity) {
        currentSize = 0;
        arr = (T[]) new Comparable[capacity + 1];
    }

    public BinaryHeap(T[] items) {
        currentSize = items.length;
        arr = (T[]) new Comparable[(currentSize + 2) * 11 / 10];

        int i = 1;
        for (T item : items) {
            arr[i++] = item;
        }
        buildHeap();
    }

    /**
     * 二叉堆的插入方法。使用上滤法。
     *
     * @param t 被插入的元素
     */
    public void insert(T t) {
        if (currentSize == arr.length - 1) {
            // 如果当前元素个数为数组长度-1，则扩容
            enlargeArray(arr.length * 2 + 1);
        }
        int hole = ++currentSize;
        // arr[0] = t初始化，最后如果循环到顶点，t.compartTo(arr[hole / 2])即arr[0]为0，循环结束
        for (arr[0] = t; t.compareTo(arr[hole / 2]) < 0; hole /= 2) {
            // 根节点的值赋值到子节点
            arr[hole] = arr[hole / 2];
        }
        // 根节点(或树叶节点)赋值为t
        arr[hole] = t;
    }

    /**
     * 寻找堆内最小值。索引1处的元素最小。
     *
     * @return
     */
    public T findMin() {
        if (isEmpty()) {
            // 这里如果堆为空，可以抛出异常。
            // throw new UnderflowException( );
        }
        // 第1位的元素最小
        return arr[1];
    }

    public T deleteMin() {
        if (isEmpty()) {
            // 这里如果堆为空，可以抛出异常。
            // throw new UnderflowException( );
        }
        T minItem = findMin();
        // 将最后一个节点赋值到根节点
        arr[1] = arr[currentSize--];
        // 从根节点执行下滤
        percolateDown(1);
        return minItem;
    }

    /**
     * 判断堆是否为空
     *
     * @return 为空返回true；否则返回false
     */
    public boolean isEmpty() {
        return currentSize == 0;
    }

    /**
     * 堆置空
     */
    public void makeEmpty() {
        currentSize = 0;
    }

    /**
     * 打印堆
     */
    public void print(){
        System.out.print("堆为:");
        for (int i = 1;arr[i] != null;i++){
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    private static final int DEFAULT_CAPACITY = 10;

    private int currentSize;
    private T[] arr;

    /**
     * 下滤
     *
     * @param hole 下滤其实的节点的索引
     */
    private void percolateDown(int hole) {
        int child;
        T tmp = arr[hole];

        for (; hole * 2 <= currentSize; hole = child) {
            child = hole * 2;
            if (child != currentSize && arr[child + 1].compareTo(arr[child]) < 0) {
                // 做子节点不为左后一个节点（说明有右节点）且右节点比做节点小，索引改为右节点节点
                child++;
            }
            if (arr[child].compareTo(tmp) < 0) {
                // 如果遍历到的这个节点比最后一个元素小
                arr[hole] = arr[child];
            } else {
                break;
            }
        }
        // 将最后一个元素补到前面的空位
        arr[hole] = tmp;
    }

    private void buildHeap() {
        for (int i = currentSize / 2; i > 0; i--) {
            percolateDown(i);
        }
    }

    /**
     * 扩容
     * @param newSize 新数组的大小
     */
    private void enlargeArray(int newSize) {
        T[] old = arr;
        arr = (T[]) new Comparable[newSize];
        for (int i = 0; i < old.length; i++) {
            arr[i] = old[i];
        }
    }
}

BinaryHeapTest.java 测试类

public class BinaryHeapTest {
    public static void main(String[] args) {
        BinaryHeap binaryHeap = new BinaryHeap();
        int[] nums = new int[]{23, 98, 34, 63, 3, 0, 87, 45};
        for (Integer num : nums) {
            binaryHeap.insert(num);
        }
        binaryHeap.print();

        System.out.println("堆是否为空:" + binaryHeap.isEmpty());


        System.out.println("获取最小值:" + binaryHeap.deleteMin());

        binaryHeap.print();

    }
}

输出：

堆为:0 23 3 45 63 34 87 98 
堆是否为空:false
获取最小值:0
堆为:3 23 34 45 63 98 87 98 

最小二叉堆实现可用。

以上就是有关二叉堆(binary heap)介绍及其Java实现。

有关[数据结构与算法]的学习内容已经上传到github，喜欢的朋友可以支持一下。
data-structures-and-algorithm-study-notes-java

站在前人的肩膀上前行，感谢以下博客及文献的支持。
《数据结构与算法分析(第3 版) 工业出版社》

什么是二叉堆(binary heap)

二叉堆是一种满足特殊性质的二叉树。具有以下性质：

1. 二叉堆是一颗完全二叉树(除叶子节点以外其余节点的左右孩子都不为空)
2. 所有节点的值都大于等于(最大堆)孩子节点的值最小堆刚好相反
   二叉堆在排序和求取top N 等问题上都有广泛的应用

实现思路（以最大堆为例）

因为堆是一颗完全二叉树，所以采用 列表 + shift_up + shift_down 的经典方式实现堆会很容易
用列表实现堆可以方便的发现:

1. 一个节点 p索引为pi 的左孩子索引 li = pi * 2 + 1
2. 一个节点 p索引为pi 的右孩子索引 ri = pi * 2 + 2
3. 一个节点 p索引为pi 的父亲索引 parent_i = （pi - 1） // 2 (向下取整)
   所以我们可以很方便的封装出获取一个节点的左右孩子和父亲节点的方法

class MaxHeap(object):

    def __init__(self):
        self.data = []

    def __left_child(self, index):
        return index * 2 + 1

    def __right_child(self, index):
        return index * 2 + 2

    def __parent(self, index):
        if index == 0:
            raise Exception('堆顶没有父亲节点')
        else:
            return (index - 1) // 2

通过上浮操作来向堆中新增元素

上浮操作就是指每次新增元素的时候将新增元素放入数组末尾，之后通过索引获取新增节点的父亲节点的索引，如果新增节点的数值比父亲节点的数值大，就将新增节点的值和父亲节点进行交换，即是上浮，不断上浮直到到堆顶整个新增操作完成，封装上浮操作如下

class MaxHeap(object):
    ......
    def __shift_up(self, index):
        while index > 0 and self.data[index] > self.data[self.__parent(index)]:
            self.data[index], self.data[self.__parent(index)] = self.data[self.__parent(index)], self.data[index]
            index = self.__parent(index)

通过下沉操作来取出堆中元素

下沉操作就是为了保证取出堆顶元素之后，其余元素可以组成新的最大堆：

1. 将堆顶元素和堆尾元素进行互换，弹出堆尾元素作为返回
2. 从堆顶开始 和其左右孩子中较大的孩子进行比较，如果比左右孩子中较大的孩子要小，就与左右孩子中较大的孩子进行互换不断下沉，直到比左右孩子中较大的元素要大的时候(堆的第二个性质)，新的最大堆就形成了，下沉操作完成
   这里注意判断一个节点是否有左右孩子，防止数组越界

class MaxHeap(object):
    ......
    def __shift_down(self, index):
    	# 先判断是否有左孩子
        while self.__left_child(index) < len(self.data):
            li = self.__left_child(index)
            lr = self.__right_child(index)
			# 再判断是否有右孩子
            if lr < len(self.data) and self.data[li] < self.data[lr]:
                j = lr
            else:
                j = li

            if self.data[index] < self.data[j]:
                self.data[index], self.data[j] = self.data[j], self.data[index]
                index = j
            else:
                break

数据结构设计&封装

1. def add(word) // return None 向Trie中添加一个单词
2. def is_empty() // return bool 询问字典树是否包含该前缀的单词
3. def size() // ruturn int 返回字典树存储单词个数 使用__len__()代替
4. def extract_max() // return e 弹出堆顶元素
5. def find_max() // return e 查看堆顶元素
6. def heapify(arr) // return None 将数组序列化为堆
7. def replace(e) // return e 替换堆顶元素
   为了保证Python语法风格，使用魔法函数实现部分功能

实现

class MaxHeap(object):

    def __init__(self, heapify = None):
        if heapify:
            self.heapify(heapify)
        else:
            self.data = []

    def __len__(self):
        return len(self.data)

    def is_empty(self):
        return len(self.data) == 0

    def __left_child(self, index):
        return index * 2 + 1

    def __right_child(self, index):
        return index * 2 + 2

    def __parent(self, index):
        if index == 0:
            raise Exception('堆顶没有父亲节点')
        else:
            return (index - 1) // 2

    def add(self, e):
        self.data.append(e)
        self.__shift_up(len(self.data) - 1)

    def __shift_up(self, index):
        while index > 0 and self.data[index] > self.data[self.__parent(index)]:
            self.data[index], self.data[self.__parent(index)] = self.data[self.__parent(index)], self.data[index]
            index = self.__parent(index)

    def extract_max(self):
        if self.is_empty():
            self.data[0], self.data[-1] = self.data[-1], self.data[0]
            res = self.data.pop()

            self.__shift_down(0)
            return res
        else:
            raise Exception('堆为空')


    def find_max(self):
        if self.is_empty():
            raise Exception('堆为空')

        return self.data[0]

    def __shift_down(self, index):
        while self.__left_child(index) < len(self.data):
            li = self.__left_child(index)
            lr = self.__right_child(index)

            if lr < len(self.data) and self.data[li] < self.data[lr]:
                j = lr
            else:
                j = li

            if self.data[index] < self.data[j]:
                self.data[index], self.data[j] = self.data[j], self.data[index]
                index = j
            else:
                break

    def replace(self, e):
        res = self.data[0]
        self.data[0] = e
        self.__shift_down(0)
        return res

    def heapify(self, arr):
        self.data = arr
        pi = self.__parent(len(arr) - 1)

        while pi >= 0:
            self.__shift_down(pi)
            pi -= 1

转载注明出处