堆(Heap)

堆是一种基于数组实现的特殊树形数据结构，它满足父节点的键值总是大于（或小于）它的子节点的键值，被称为大根堆（或小根堆）。堆经常用来实现优先队列和堆排序等算法。

特性

• 很容易找到父节点索引：parentIndex = (index - 1) / 2;

ADT(MinHeap)

public void add(Item x);
public Item getSmallest();
public Item removeSmallest();
public int size();

堆排序实现

控制台输出：

点击"运行代码"查看输出...

输出：

试试看

在"输出"框中输入 heapSort([64, 34, 25, 12, 22, 11, 90]) 来测试不同的数组！

堆排序特点:

• 时间复杂度: O(n log n)
• 空间复杂度: O(1)
• 不稳定排序
• 原地排序算法