堆 Heap
1. 堆Heap
定义
堆是一颗安全二叉树，其结点含有Comparable的对象。在最大堆中，每个结点的对象都大于等于它的子孙结点中的对象。
public interface MaxHeapInterface<T extends Comparable<? super T>> {
public void add(T newEntry);
public T removeMax();
public T getMax();
public boolean isEmpty();
public int getSize();
public void clear();
}
2. 用数组表示堆
用数组表示完全二叉树：一个完全二叉树在其倒数第二层以上是满的，并且其最后一层上的叶子结点是从左到右填满的。因此，指导最后一片叶子，完全二叉树中没有空洞。
如果一颗二叉树是完全的，使用数组而不是链表会更好。可以使用层序遍历将这棵二叉树的数据存放到一个数组中的连续位置。这种表示可以容易地找到一个结点的双亲或孩子中的数据。如果从数组的索引1开始存放二叉树，即跳过数组的第一个位置，则数组索引i处结点的：
双亲在索引i/2处，除非该结点是根节点（i为1）；
子结点在索引2i与2i+1处。
MaxHeap类
public class MaxHeap<T extends Comparable<? super T>> implements
MaxHeapInterface<T>, Serializable {
private T[] heap; // 存放堆元素的数组
private int lastIndex; // 最后一个元素的索引
private static final int DEFAULT_INITIAL_CAPACITY = 25;
public MaxHeap() {
this(DEFAULT_INITIAL_CAPACITY);
}
public MaxHeap(int initialCapacity) {
heap = (T[]) new Comparable[initialCapacity + 1];
lastIndex = 0;
}
// 插入元素
public void add(T newEntry) {
// 代码如下
}
public T removeMax() {
// 代码如下
}
public T getMax() {
T root = null;
if (isEmpty())
root = heap[1];
return root;
}
public boolean isEmpty() {
return lastIndex < 1;
}
public int getSize() {
return lastIndex;
}
public void clear() {
for (; lastIndex > -1; lastIndex--)
heap[lastIndex] = null;
lastIndex = 0;
}
}
This chapter requires login to view full content. You are viewing a preview.
Login to View Full ContentCourse Curriculum
1
编程根基：数据结构、算法与系统基础
掌握常用数据结构与算法思想，理解操作系统进程/内存管理及网络 TCP/IP 模型，为后续性能分析、并发设计和系统调优提供底层认知支撑。
2
Java 内核：JVM 与并发编程
深入 JVM 内存布局、垃圾回收机制与 Java 内存模型，熟练使用并发工具类与锁原语，写出线程安全、低延迟、可诊断的高性能 Java 代码。
3
框架与 I/O：Spring、Netty 与 Web 容器
理解 Spring Boot 自动装配、AOP 与事务原理，掌握 Netty Reactor 模型及 Tomcat 连接处理机制，构建高内聚、易扩展的应用服务层。
4
高性能中间件：消息、缓存与存储
熟练运用 MySQL 索引/事务、Redis 缓存策略、Kafka/RocketMQ 消息可靠性，以及 ZooKeeper 分布式协调，搭建稳定、解耦的分布式数据底座。
5
架构能力：高可用、DDD 与系统设计
基于领域驱动设计划分限界上下文，结合限流、熔断、多活容灾等手段，设计可演进、可观测、故障自愈的大规模业务系统。
6
云原生：容器化、可观测性与工程效能
通过 Docker/K8s 实现弹性部署，集成 Metrics/Logs/Traces 构建可观测体系，推动 DevOps 与自动化，让架构在云上持续交付与进化。
Speaker
Songran Zhang
@Aliyun | Qwen Chat
Songran Zhang is senior systems architect at Aliyun, a speaker, and an author. Over the past 15 years, he's mastered architectures from cloud-native systems to AI-powered LLM platforms, building deep technical expertise across large-scale, high-availability systems.
