面向对象的数据结构 – 以 Heap 为例
之前学数据结构时都是使用 C/C++ 实现，习惯了面向过程的方式再使用面向对象还有一点点不知所措。
借着 操作系统短进程优先算法 的机会第一次尝试使用 Java 实现了一个简单的数据结构。
这里实现的 Heap 只包含了最基础的排序，没有添加任意删除等操作。
Motivation
在此之前，有个还没有公开发表的 flag，想在这学期结束前后写一个运行在 C51/STM32 上的简易的操作系统（尽管这学期才过了四分之一，但我已经可以预见这个 flag 要鸽了），因此最初的选择就是用 C 写。
可经过复习后发现想要实现操作系统级的调度算法有些许困难，如果只是实现算法思想，语言只是工具平台而已。用 C 当然可以，想着写习惯了面向过程还是应该试一下面向对象的方式。
Realization
Heap 的实现还是很简单的，这里整理了一下以前的笔记：
定义
堆是一颗完全二叉树，树中的每一个结点都大于（小于）等于其父亲节点的值，由此引出两种堆：
- 大根堆：父亲结点的值大于或等于左右节点
- 小根堆：父亲结点的值小于或等于左右结点
存储方式
由于堆是一个完全二叉树，可以使用数组进行存储，减少空间的浪费。（但也可以使用链式存储）
因为 Java 的链式存储没有写过，这里直接使用了 ArrayList 替代数组进行存储
维护
up 和 down 是两个基础的维护操作，指的是元素在树中的深度变化。两个操作的最坏时间复杂度均为$O(log h)$
在 up 和 down 操作里的 swap 和 compare 是两个自定义的方法，这里的 PCB 是一个自定义的对象，直接沿用的操作系统实验中的代码片段，具体定义可以参考这里：Operating Systems: Lab 1 SPF(Shortest-Process-First)
public void swap(int u, int v)
{
PCB Temp = heap.get(u);
heap.set(u, heap.get(v));
heap.set(v, Temp);
}
public int compare(int u, int v)
{
PCB pcb1 = this.heap.get(u);
PCB pcb2 = this.heap.get(v);
if (pcb1.getRemaining() == pcb2.getRemaining())
{
if(pcb1.getQueueID() > pcb2.getQueueID())
{
return 1;
}else{
return -1;
}
}
if (pcb1.getRemaining() > pcb2.getRemaining())
{
return 1;
}
if (pcb1.getRemaining() < pcb2.getRemaining())
{
return -1;
}
System.out.println("Error, please check the method!");
return 0;
}
up操作
up操作实际上就是对比自己与父节点的大小，从而进行交换，其中使用while或递归进行书写，可以保证把当前结点调整到合适的位置。
public void up(int point)
{
while (point != 0 && (this.compare(point, point / 2) < 0)) {
this.swap(point, point / 2);
point /= 2;
}
}
down操作
down操作实际上就是用自己和两个子节点进行比较，选择较大的子节点然后和父亲结点交换，其中使用while或者递归的方式书写，可以保证结点被放到合适的位置。
public void down(int point)
{
int size=heap.size()-1;
while(point * 2 <= size)
{
int temp = point;
if(point * 2 <= size && (this.compare(point, point * 2) > 0))
{
temp = 2 * point;
}
if(point * 2 + 1 <= size && (this.compare(temp,point * 2 + 1) > 0))
{
temp = 2 * point + 1;
}
if(point != temp)
{
this.swap(point,temp);
point = temp;
}else break;
}
}
基本操作
Heap 的操作其实也不算少，这里只根据实际实现了三个：
建堆与插入
想要使用数组维护 Heap，需要让数组的下标从 1 开始，对于 ArrayList 来说需要预先插入一个空节点，这里在 Constructor 中进行了处理。
Heap()
{
heap = new ArrayList<PCB>();
PCB emptyPCB = new PCB(-1);
heap.add(emptyPCB);
order = 0;
}
之后的建堆过程是通过不断的插入实现的。
public void push(PCB newNode)
{
newNode.setQueueID(order);
heap.add(newNode);
order++;
this.up(heap.size() - 1);
}
查询最值
由于堆的性质，查找最小(最大)值只需要$O(1)$的操作
public PCB top()
{
if(this.empty()) return null;
else return heap.get(1);
}
删除最值
删除时需要三个操作维护堆的合法性：
- 将最后一个元素赋值给堆顶元素
- 将最后一个元素删除
- 对堆顶元素进行
down()操作
public void pop()
{
int size = heap.size();
heap.set(1,heap.get(size - 1));
heap.remove(size-1);
down(1);
}
Thinking
从抽象到更抽象，面向对象的思想确实是一个巨大的进步，受限于个人水平，在实现中还带有一些面向过程的风格，技术上还未涉及泛型、接口等内容，再次回忆 C++ 的 STL，也是从 具体 到 抽象 的过程，从学习的角度在一定阶段是要避免使用的，但是在实际的解决问题中 抽象/面向对象 的思的的确确为我们提供了便利。
Code
import java.util.*;
public class Heap
{
ArrayList<PCB> heap;
private static int order;
/*
* Initialize the heap.
* In order make the index of first process is one,
* we need use the constructor to push 'empyt process' to the heap.
*/
Heap()
{
heap = new ArrayList<PCB>();
PCB emptyPCB = new PCB(-1);
heap.add(emptyPCB);
order = 0;
}
/*
* Swap the element in ArrayList.
*/
public void swap(int u, int v)
{
PCB Temp = heap.get(u);
heap.set(u, heap.get(v));
heap.set(v, Temp);
}
/*
* Compare the element in ArrayList.
* The first keyword is remaining time,
* The second keyword is queue id.
*
* Queue id is the order of the element push the heap.
*
* As we know that remaining time may be the same, but queueID is unique.
* So according to the queueID to compare can always be true.
*/
public int compare(int u, int v)
{
PCB pcb1 = this.heap.get(u);
PCB pcb2 = this.heap.get(v);
if (pcb1.getRemaining() == pcb2.getRemaining())
{
if(pcb1.getQueueID() > pcb2.getQueueID())
{
return 1;
}else{
return -1;
}
}
if (pcb1.getRemaining() > pcb2.getRemaining())
{
return 1;
}
if (pcb1.getRemaining() < pcb2.getRemaining())
{
return -1;
}
System.out.println("Error, please check the method!");
return 0;
}
/*
* We need two operations to make the heap is legal.
* The purpose of up() is make the lesser element to upper layer.
* The purpose of down() is make the bigger element to lower layer.
*/
public void up(int point)
{
while (point != 0 && (this.compare(point, point / 2) < 0)) {
this.swap(point, point / 2);
point /= 2;
}
}
public void down(int point)
{
int size=heap.size()-1;
while(point * 2 <= size)
{
int temp = point;
if(point * 2 <= size && (this.compare(point, point * 2) > 0))
{
temp = 2 * point;
}
if(point * 2 + 1 <= size && (this.compare(temp,point * 2 + 1) > 0))
{
temp = 2 * point + 1;
}
if(point != temp)
{
this.swap(point,temp);
point = temp;
}else break;
}
}
/*
* There is some common method of data structure.
*/
public void push(PCB newNode)
{
newNode.setQueueID(order);
heap.add(newNode);
order++;
this.up(heap.size() - 1);
}
public PCB top()
{
if(this.empty()) return null;
else return heap.get(1);
}
public void pop()
{
int size = heap.size();
heap.set(1,heap.get(size - 1));
heap.remove(size-1);
down(1);
}
public boolean empty()
{
if(heap.size() > 1)
{
return false;
}else{
return true;
}
}
public int size()
{
return heap.size();
}
}
评论