SpringBoot电商项目实战Day2 堆（优先队列）

学习目标：

1.对数据库的表进行设计

2.进行项目技术选型

3.对项目进行初始化，生成逆向文件

4.打通数据库链路

5.配置log4j2日志组件

6.完成了向堆中添加元素SiftUp,从堆中取出元素SiftDown

---

学习内容：

完成了大体的数据库设计与项目初始化的工作。

学习了如何操作堆进行添加与取出操作。

public class MaxHeap> {
    private Array data;

    public MaxHeap(int capacity) {
        data = new Array<>(capacity);
    }

    public MaxHeap() {
        data = new Array<>();
    }

    //返回堆中的元素个数
    public int size() {
        return data.getSize();
    }

    //返回一个布尔值，表示堆中是否为空
    public boolean isEmpty() {
        return data.isEmpty();
    }

    //返回完全二叉树的数组表示中，一个索引所表示的元素的父亲结点的索引
    private int parent(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("index-0 doesn't have parent.");
        }
        return (index - 1) / 2;
    }

    //返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子结点的索引
    private int leftChild(int index) {
        return index*2+1;
    }
    //返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子结点的索引
    private int rightChild(int index) {
        return index*2+2;
    }

    //向堆中添加元素
    public void add(E e) {
        data.addLast(e);
        siftUp(data.getSize() - 1);
    }

    private void siftUp(int k) {
        while (k > 0&&data.get(parent(k)).compareTo(data.get(k))<0) {
            data.swap(k, parent(k));
            k = parent(k);
        }
    }

    //看堆中的最大元素
    public E findMax() {
        if (data.getSize() == 0) {
            throw new IllegalArgumentException("Can not findMax when heap is empty.");
        }
        return data.get(0);
    }
    //取出堆中最大元素
    public E extractMax() {
        E ret = findMax();
        data.swap(0, data.getSize() - 1);
        data.removeLast();
        siftDown(0);
        return ret;
    }

    private void siftDown(int k) {
        while (leftChild(k) < data.getSize()) {
            int j = leftChild(k);
            if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
                j = rightChild(k);
            }
            //data[j]是leftChild和rightChild中的最大值
            if (data.get(k).compareTo(data.get(j)) >= 0) {
                break;
            }
            data.swap(k, j);
            k = j;
        }
    }
}

---

学习时间：

17：30-23：45

---

学习产出：

了解了一个项目初始时的一些工作，同时对于数据库的表设计有了一定的了解，渐渐熟悉了应用SpringBoot框架进行项目的搭建。