面向对象的数据结构 – 以 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);
}

				

					
				
				

					
				
				

					
				
				

					
				
			

删除最值

删除时需要三个操作维护堆的合法性：

1. 将最后一个元素赋值给堆顶元素
2. 将最后一个元素删除
3. 对堆顶元素进行 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();
    }
 
}