阅读 495

《漫画算法》读后笔记(一)

看完了《漫画算法—小灰的算法之旅》第一遍,觉得有些意犹未尽,因此第二次重温时,打算开始做一些笔记,这样可以加深自己对算法知识的理解,也能对没有看过这本书的朋友提供一些帮助。本文为了各位看官方便,由一篇该为四篇,这是第一篇———算法基础

一、基础概念

算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度时间复杂度来衡量。

以上来自百度百科

算法除了上述具体概念外,对于程序员而言还有很多应用场景,如运算、查找、排序、最优决策等,但是对于大多数像我这样的程序员而言最重要的还是面试,因为工作中对算法运用的不多,学习这本书主要是增加自己的内功和面试的时候不至于太心慌!

1.时间复杂度 记作T(n)

具体原则有三个:

  • 如果运行时间是常数量级,则用常1表示
  • 只保留函数的最高阶项
  • 如果最高阶项存在,则省去最高阶项前面的系数

以下为具体示例:

执行次数是线性的

假设你有n颗瓜子,每三分钟吃掉一颗,那么需要多久才能吃完呢?

耗时:3*n


fun eat1(n:Int){
    for(i in 0 until n){
        Thread.sleep(1000)
        println("等待第一分钟")
        Thread.sleep(1000)
        println("等待第二分钟")
        Thread.sleep(1000)
        println("第三分钟 吃一颗瓜子")
    }
}

最高阶项为3n,则省去系数3,时间复杂度表示为:
T(n) = O(n)
复制代码

执行次数是用对数计算的

假设你有16颗瓜子,每五分钟吃掉一半,那么需要多久才能吃完呢?

耗时 5*logn

注意: logn指的是n的对数,比如24次方等于16,则16的对数则是4


fun eat2(n:Int){
    var num = n
    for (i in 0 until n) {
        if(i<num)break
        Thread.sleep(1000)
        println("等待第一分钟")
        Thread.sleep(1000)
        println("等待第二分钟")
        Thread.sleep(1000)
        println("等待第三分钟")
        Thread.sleep(1000)
        println("等待第四分钟")
        Thread.sleep(1000)
        println("第五分钟 吃一半瓜子")
        num = num / 2
    }
}

最高阶项为 5logn,则省去系数5,时间复杂度表示为:
T(n) = O(logn)

复制代码

执行次数是常量

你有1颗瓜子和3颗花生,吃一颗花生需要2分钟,吃一颗瓜子需要1分钟,问你吃掉瓜子需要多久?

耗时 1分钟

fun eat3(){
    Thread.sleep(1000)
    println("等待第一分钟")
    println("吃一颗瓜子")
}
只有常数量级,则时间复杂度表示为:
T(n) = O(1)
复制代码

执行次数是多项式计算的

你有n颗瓜子,吃第一颗瓜子需要1分钟,吃第二颗瓜子需要2分钟,吃第三颗瓜子需要3分钟,依次类推。问,吃完n颗瓜子需要多久?

耗时 0.5*n^2+0.5n

fun eat4(n:Int){
    for (i in 0 until n){
            for (j in 0 until i){
                println("等待1分钟")
            }
            println("吃1颗瓜子")
        }
}
最高阶项是0.5n^2,则时间复杂度表示为:
T(n) = O(n^2)
复制代码

结论: 比较后得出结论如下:

O(1) < O(logn) < O(n) < O(n^2)

2.空间复杂度 记作O(n)

空间复杂度和上面的时间复杂度类似,有以下四种类型:

常量类型

算法存储空间与输入规模大小没有直接关系,记作O(1)

fun fun1(n:Int){
    var value = 3
    ...
}
复制代码

线性空间

当算法分配的空间是一个线性的集合(如数组),且集合的大小和输入的规模成正比,记作O(n)

fun fun2(n:Int){
    var array = IntArray(n)
    ...
}
复制代码

二维空间

当算法分配的空间是一个二维数组集合,且集合的长度和宽度与输入的规模成正比,记作O(n^2)

void fun3(n:Int){
    val array = Array(n){return@Array IntArray(n)}
    ...
}
复制代码

递归空间

执行递归所需要的内存空间和递归的深度成正比,记作O(n)

fun fun4(n:Int){
    if(n<=1){
        return
    }
    fun4(n-1)
}
复制代码

3.数据结构 data structure

  • 线性结构

    • 数组

    数组 array,是有限个相同类型的变量所组成的有序集合,数组中的每一个变量被称之为元素。优点,因为其在内存在顺序存储,因此拥有非常高效的随机访问能力,只要通过下标就可以直接获取元素,缺点是插入会导致大量数据被迫移动,影响效率(例如HashMap扩容)。适合读操作多,写操作少的业务场景。

    • 链表

    链表是一种数据结构,分为单链表和双链表。下面这张图就是单链表

    如果觉得还是抽象的话,那我们一起看看代码吧!

/**
 * <p>文件描述:链表的基本操作<p>
 * <p>@author 烤鱼<p>
 * <p>@date 2019/10/17 0017 <p>
 * <p>@update 2019/10/17 0017<p>
 * <p>版本号:1<p>
 *
 */
// 单链表
data class Node(var data:Int,var next: Node? = null)
// 双链表
data class DoubleNode(var data: Int, var prev: DoubleNode?, var next: DoubleNode?)

class Test {
    // 头节点指针
    private  var head: Node? = null
    // 尾节点指针
    private  var last: Node? = null
    // 链表实际长度
    private var size = 0

    // 插入链表元素
    fun insert(data:Int,index:Int){
        if(index<0 || index>size){
            throw IndexOutOfBoundsException("超出链表节点范围")
        }
        val insertNode = Node(data)
        if(size == 0){
            // 空链表
            head = insertNode
            last = insertNode
        }else if(index == 0){
            // 插入头部
            insertNode.next = head
            head = insertNode
        }else if (size == index){
            // 插入尾部
            last?.next = insertNode
            last = insertNode
        }else{
            // 插入中间
            val prevNode = getNode(index-1)
            insertNode.next = prevNode?.next
            prevNode?.next = insertNode
        }
        size++
    }

    fun remove(index: Int): Node?{
        if(index<0 || index>=size){
            throw IndexOutOfBoundsException("超出链表节点范围")
        }
        var removeNode: Node? = null
        if(index == 0){
            // 删除头节点
            removeNode = head
            head = head?.next
        }else if (index == size-1){
            // 删除尾节点
            removeNode = getNode(index-1)
            removeNode?.next = null
            last = removeNode

        }else {
            // 删除中间节点
            val prevNode = getNode(index-1)
            removeNode = prevNode?.next
            val nextNode = prevNode?.next?.next
            prevNode?.next = nextNode
        }
        size--
        return removeNode
    }
    fun outPut(){
        var  temp = head
        while (temp != null){
            print(temp.data)
            temp = temp.next
        }
    }

    /**
     * 链表查找元素
     */
    private fun getNode(index: Int): Node? {
        if(index<0 || index>=size){
            throw IndexOutOfBoundsException("超出链表节点范围")
        }
        var temp: Node? = head
        for (i in 0 until index){
            temp = temp?.next
        }
        return temp
    }


}
复制代码

测试一下上面的这个单链表:

/**
 * <p>文件描述:数据结构测试<p>
 * <p>@author 烤鱼<p>
 * <p>@date 2019/10/17 0017 <p>
 * <p>@update 2019/10/17 0017<p>
 * <p>版本号:1<p>
 *
 */
class DataStructure {
    @org.junit.Test
    fun testLinkedList() {
        val test = Test()
        test.insert(3,0)
        test.outPut()
        println()
        test.insert(7,1)
        test.outPut()
        println()
        test.insert(9,2)
        test.insert(5,3)
        test.outPut()
        println()
        test.insert(4,2)
        test.outPut()
        println()
        test.remove(0)
        test.outPut()
    }
}
复制代码

运行结果:

3
37
379
3795
37495
7495
复制代码

链表和数组相比,数组的优势还是快速定位元素,适合读操作多,写操作少的业务场景;链表则相对于删除和尾部插入更合适,因此适用于频繁插入删除的业务情景

java.util.Stack是一种先入后出的线性数据结构,如图:

package java.util;

/**
 * The <code>Stack</code> class represents a last-in-first-out
 * (LIFO) stack of objects. It extends class <tt>Vector</tt> with five
 * operations that allow a vector to be treated as a stack. The usual
 * <tt>push</tt> and <tt>pop</tt> operations are provided, as well as a
 * method to <tt>peek</tt> at the top item on the stack, a method to test
 * for whether the stack is <tt>empty</tt>, and a method to <tt>search</tt>
 * the stack for an item and discover how far it is from the top.
 * <p>
 * When a stack is first created, it contains no items.
 *
 * <p>A more complete and consistent set of LIFO stack operations is
 * provided by the {@link Deque} interface and its implementations, which
 * should be used in preference to this class.  For example:
 * <pre>   {@code
 *   Deque<Integer> stack = new ArrayDeque<Integer>();}</pre>
 *
 * @author  Jonathan Payne
 * @since   JDK1.0
 */
public class Stack<E> extends Vector<E> {
    /**
     * Creates an empty Stack.
     */
    public Stack() {
    }

    /**
     * Pushes an item onto the top of this stack. This has exactly
     * the same effect as:
     * <blockquote><pre>
     * addElement(item)</pre></blockquote>
     *
     * @param   item   the item to be pushed onto this stack.
     * @return  the <code>item</code> argument.
     * @see     java.util.Vector#addElement
     */
    public E push(E item) {
        addElement(item);

        return item;
    }

    /**
     * Removes the object at the top of this stack and returns that
     * object as the value of this function.
     *
     * @return  The object at the top of this stack (the last item
     *          of the <tt>Vector</tt> object).
     * @throws  EmptyStackException  if this stack is empty.
     */
    public synchronized E pop() {
        E       obj;
        int     len = size();

        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }

    /**
     * Looks at the object at the top of this stack without removing it
     * from the stack.
     *
     * @return  the object at the top of this stack (the last item
     *          of the <tt>Vector</tt> object).
     * @throws  EmptyStackException  if this stack is empty.
     */
    public synchronized E peek() {
        int     len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }

    /**
     * Tests if this stack is empty.
     *
     * @return  <code>true</code> if and only if this stack contains
     *          no items; <code>false</code> otherwise.
     */
    public boolean empty() {
        return size() == 0;
    }

    /**
     * Returns the 1-based position where an object is on this stack.
     * If the object <tt>o</tt> occurs as an item in this stack, this
     * method returns the distance from the top of the stack of the
     * occurrence nearest the top of the stack; the topmost item on the
     * stack is considered to be at distance <tt>1</tt>. The <tt>equals</tt>
     * method is used to compare <tt>o</tt> to the
     * items in this stack.
     *
     * @param   o   the desired object.
     * @return  the 1-based position from the top of the stack where
     *          the object is located; the return value <code>-1</code>
     *          indicates that the object is not on the stack.
     */
    public synchronized int search(Object o) {
        int i = lastIndexOf(o);

        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }

    /** use serialVersionUID from JDK 1.0.2 for interoperability */
    private static final long serialVersionUID = 1224463164541339165L;
}
复制代码
  • 队列

队列和栈极其相似,二者的区别点在于栈是先进后出(FILO),而队列是先入先出(FIFO

有意思的是我们可以通过数组来实现这个数据操作,且避免了整体数据迁移的麻烦!

package com.vincent.algorithmapplication.data_structure

import java.lang.Exception

/**
 * <p>文件描述:自定义对列的实现<p>
 * <p>@author 烤鱼<p>
 * <p>@date 2019/10/23 0023 <p>
 * <p>@update 2019/10/23 0023<p>
 * <p>版本号:1<p>
 *
 */
class MyQueue (capaicty:Int){
    private  var array:IntArray
    var front = 0
    var rear = 0
    init {
        array = IntArray(capaicty)
    }

    fun enQueue(element:Int){
        if((rear+1)%array.size == front){
            throw Exception("队列已满")
        }
        array[rear] = element
        rear = (rear+1)%array.size
    }

    fun deQueue():Int{
        if(rear == front){
            throw Exception("队列已空")
        }
        val deQueueElement = array[front]
        front = (front+1)%array.size
        return deQueueElement
    }

    fun output(){
        for (i in array){
            print(i)
        }
        println()
    }
}

//测试:
    fun testMyQueue(){
        val myQueue = MyQueue(6)
        myQueue.enQueue(3)
        myQueue.enQueue(6)
        myQueue.enQueue(2)
        myQueue.enQueue(7)
        myQueue.enQueue(5)
        myQueue.deQueue()
        myQueue.enQueue(9)
        myQueue.deQueue()
        myQueue.enQueue(4)
        myQueue.deQueue()
        myQueue.enQueue(1)
        myQueue.output()
    }

复制代码

测试结果:

412759

复制代码

栈的应用业务对于历史操作的记录,比如返回上一步,而队列用于历史记录顺序的保存,比如爬虫脚本抓取的地址顺序存放,后面操作的时候顺序读取。

扩展:

双端队列——结合了栈和队列的特点,可从对头或者队尾插入或者删除

优先队列——根据元素的优先级决定谁最先出队

  • 哈希表

哈希表也叫做散列表,这种数据结构提供键(key)和值(value)的映射关系来实现数据存取。 主要三个知识点:

  • 哈希函数——将键值转化为值的数组下标(不是说值就是数组储存,直接抽象这么理解思路即可)
  • 写操作(哈希冲突)与读操作 写操作的时候难免遇到两个不同的键值转化结果是同一个下标值,此时有两种处理方式,一种是安卓中的ThreadLocal使用的开放寻址法,一种是HashMap中使用的链表法。读操作就简单了,根据写操作选择对应的方法取值即可
  • 扩容 散列表空间即将达到饱和时需要进行扩容,以HashMap举例:
HashMap.Size 散列表空间
Capacity HashMap 当前已用空间
LoadFactor HashMap 负载因子,默认值0.75
HashMap.Size >= Capacity * LoadFactor
复制代码

扩容时除了需要将原先的空间扩大两倍以外,还要将所有的值重新经过哈希函数定位保存。

看了这部分内容的时候,让我有一种重新去翻看HashMap源码的冲动

  • 树 后面第二部分单独介绍
  • 图 处理类似数据库一样复杂的多对的关系的数据结构,书中没有给出具体案例。
  • 其它
    • 位图 后面的算法当中有用到

除了作者划分的这几个类型,我们还可以看看百度对数据结构的划分:

二、数和二叉树那些事

1.什么是树(tree

数据结构中的,指的是n(n>=0)个节点的有限集。当n=0时称为空树。在任意一个非空树中,有以下特点:

  • 有且仅有一个特定的称为根的节点。
  • n>1时,其余节点可分为m(m>0)个互不相交的有限集,每一个有限集本身又是一个树,并称为根的子树。
    树状图

在上图中,节点1根节点,像节点7这样没有孩子节点的称之为叶子节点,其中的节点24589又构成了节点1子树

节点4的上一级节点是它的父节点,节点4衍生出来的节点8和节点9属于它的孩子节点,也可称为左孩子和右孩子,节点8和节点9由于是同一个父节点,因此他们又互为兄弟节点

树的最大层级数称为树的高度或者深度,图中树的深度明显是4

二叉树主要是一种逻辑思维,其代码具体实现(也称为物理存储结构)既支持链式存储也支持数组存储,当然我们一般都是数组存储。

上面的概念不用死记硬背,知道是什么意思即可,主要是方便后续文章表达,避免各位看官老爷一头雾水!

2.什么是二叉树(binart)?

准备好,一堆概念即将来袭!

二叉树是树的一种特殊形式,(这里的二叉并非骂人),顾名思义,树的每个节点最多有2个孩子节点。特别强调,这里表达的是最多2个,也包含只有1个节点或者没有子节点的情况。

二叉树还有多种表现形式,比如:

  • 满二叉树(有文章也称为完美二叉树)

二叉树的所有非叶子节点均存在左右孩子,并且所有叶子节点都在同一层级上,那么这个数就是满二叉树!如果硬要用一句话解释:只要你有孩子,你就必然是有两个孩子!如果看不懂也没有关系,咱们直接看图!

  • 完全二叉树

对一个有n个节点的二叉树,按层级序号编写,则所有节点的编号为从1n。如果这个数的所有节点和同样深度的满二叉树的编号从1n的节点位置相同,则这个二叉树为完全二叉树。如果看不懂,那就对了。我最初也看不懂,直接看图,再回头来看看定义!

树状图
建议和满二叉树的示例图一起看更容易理解。

  • 二叉查找树

二叉查找树,也称为二叉排序树(Binary Sort Tree),还有一个名字是二叉搜索树,指的是在二叉树的基础上增加了三个条件:

  • 如果左子树不为空,则左子树上所有的节点的值小于根节点的值
  • 如果右子树不为空,则右子树上所有节点的值均大于根节点的值
  • 左右子树都是二叉查找树

在节点如上图分布相对均衡的时候,二叉查找树的时间复杂度是O(logn),如果节点分布如下图的话,其时间复杂度将达到O(n)

  • 红黑树Red Black Tree

红黑树是一种平衡二叉树,除了满足二叉查找树的规定外,还有自己的5点规定:

  • 节点是红色或黑色
  • 根节点是黑色
  • 每个叶子节点都是黑色的空节点(NIL节点)
  • 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
  • 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
    简单来讲,红黑树通过左旋转、右旋转、变色三种方式组合使用来实现自平衡的,具体过程建议查看原文什么是红黑树

3.二叉树的遍历

二叉树由于其自身的复杂性,其遍历也有多种方式,从宏观的角度可以深度优先遍历广度优先遍历,从节点之间的位置关系来分,有以下四种:

  • 前序遍历 (深度优先遍历) 输出顺序:根节点-->左子树-->右子树
  • 中序遍历 (深度优先遍历) 左子树-->跟节点-->右子树
  • 后序遍历 (深度优先遍历) 左子树-->右子树-->跟节点
  • 层序遍历 (广度优先遍历) 根节点-->叶子节点

概念说起来抽象,咱们直接见代码:

/**
 * <p>文件描述:二叉树通过递归的方式实现的遍历<p>
 * <p>@author 烤鱼<p>
 * <p>@date 2019/10/25 0025 <p>
 * <p>@update 2019/10/25 0025<p>
 * <p>版本号:1<p>
 *
 */

// 二叉树实体
data class TreeNode(val data: Int) {
    var leftChild: TreeNode? = null
    var rightChild: TreeNode? = null
}

object TreeSort {
    fun createBinaryTree(inputList: LinkedList<Int?>?): TreeNode? {
        if (inputList == null || inputList.isEmpty()) {
            return null
        }
        var node: TreeNode? = null
        var data = inputList?.removeFirst()
        if (data != null) {
            node = TreeNode(data)
            node.leftChild = createBinaryTree(inputList)
            node.rightChild = createBinaryTree(inputList)
        }
        return node

    }

    // 二叉树前序排列
    fun preOrderTraveral(node: TreeNode?) {
        if (node == null) return
        print(node.data)
        preOrderTraveral(node.leftChild)
        preOrderTraveral(node.rightChild)
    }


    // 二叉树中序排列
    fun inOrderTraveral(node: TreeNode?) {
        if (node == null) return
        inOrderTraveral(node.leftChild)
        print(node.data)
        inOrderTraveral(node.rightChild)
    }


    // 二叉树后序排列
    fun postOrderTraveral(node: TreeNode?) {
        if (node == null) return
        postOrderTraveral(node.leftChild)
        postOrderTraveral(node.rightChild)
        print(node.data)
    }
    
    
     // 二叉树层序遍历
    fun levelOrderTraversal(node: TreeNode?){
        val queue = LinkedList<TreeNode>()
        queue.offer(node)
        while (queue.isEmpty().not()){
            val itemTreeNode = queue.poll()
            print(itemTreeNode.data)
            if(itemTreeNode.leftChild != null){
                queue.offer(itemTreeNode.leftChild)
            }
            if(itemTreeNode.rightChild != null){
                queue.offer(itemTreeNode.rightChild)
            }
        }

    }

    // 二叉树前序排列 栈
    fun preOrderTraveralWithStack(node: TreeNode?) {
        val stack = Stack<TreeNode>()
        var root = node
        while (root != null || stack.isEmpty().not()) {
            while (root != null) {
                print(root.data)
                stack.push(root)
                root = root.leftChild
            }
            while (stack.empty().not()) {
                root = stack.pop()
                root = root.rightChild
                if (root != null) {
                    break
                }
            }
        }
    }
    // 二叉树中序排列 栈
    fun inOrderTraveralWithStack(node: TreeNode?) {
        val stack = Stack<TreeNode>()
        var root = node
        while (root != null || stack.isEmpty().not()) {
            while (root != null) {
                stack.push(root)
                root = root.leftChild
            }
            while (stack.empty().not()) {
                root = stack.pop()
                print(root.data)
                root = root.rightChild
                if (root != null) {
                    break
                }
            }
        }
    }

    // 二叉树后序排列 栈
    fun postOrderTraveralWithStack(node: TreeNode?) {
        val stack = Stack<TreeNode>()
        var root = node
        while (root != null || stack.isEmpty().not()) {
            while (root != null) {
                stack.push(root)
                root = root.leftChild
            }
            while (stack.empty().not()) {
                root = stack.pop()
                if (root?.rightChild != null) {
                    val parent = TreeNode(root.data)
                    stack.push(parent)
                    root = root.rightChild
                    break
                } else {
                    print(root.data)
                    root = null
                }
            }
        }
    }
}
复制代码

测试代码:

fun sortTreeNode() {

    val inputList = LinkedList<Int?>()
    inputList.addAll(arrayListOf(1, 3, 9, null, null, 5, null, null, 7, null, 8))
    val treeNode = TreeSort.createBinaryTree(inputList)
    println("前序排列")
    TreeSort.preOrderTraveral(treeNode)
    println()
    println("前序排列 栈")
    TreeSort.preOrderTraveralWithStack(treeNode)
    println()
    println("中序排列")
    TreeSort.inOrderTraveral(treeNode)
    println()
    println("中序排列 栈")
    TreeSort.inOrderTraveralWithStack(treeNode)
    println()
    println("后续排列")
    TreeSort.postOrderTraveral(treeNode)
    println()
    println("后序排列 栈")
    TreeSort.postOrderTraveralWithStack(treeNode)
    println()
    println("层序遍历")
    TreeSort.levelOrderTraversal(treeNode)
}
复制代码

运行结果:

前序排列
139578
前序排列 栈
139578
中序排列
935178
中序排列 栈
935178
后续排列
953871
后序排列 栈
953871
层序遍历
137958
复制代码

数据内容:

注意:书中的“二叉树非递归前序遍历”代码有个小错误,循环中没有置空treeNode导致有元素丢失。 这部分代码如果思路不清楚,不妨跟着断点,看看代码运行逻辑。

4.什么是二叉堆?

二叉堆其实就是一种特殊的完全二叉树,它有两个类型:

  • 最大堆

最大堆的任何一个父节点的值,都大于或等于它左右孩子的节点的值

  • 最小堆

最大堆的任何一个父节点的值,都小于或等于它左右孩子的节点的值

观察堆顶元素得知,最大堆的对顶元素是整个堆中的最大元素,反之,最小堆的对顶是整个堆中最小的元素

代码实现:

/**
 * <p>文件描述:二叉堆的实现<p>
 * <p>@author 烤鱼<p>
 * <p>@date 2019/10/27 0027 <p>
 * <p>@update 2019/10/27 0027<p>
 * <p>版本号:1<p>
 *
 */
object BinaryHeap {
    // “上浮”调整(插入节点排序)
    fun upAdjust(array: IntArray){
        var childIndex = array.size-1
        var parentIndex = (childIndex-1)/2
        var temp = array[childIndex]
        while (childIndex>0 && temp<array[parentIndex]){
            array[childIndex] = array[parentIndex]
            childIndex = parentIndex
            parentIndex = (parentIndex-1)/2
        }
        array[childIndex] = temp
    }

    // “下沉”调整 (删除节点)
    private fun downAdjust(array: IntArray,index:Int,length:Int){
        var parentIndex = index
        var temp = array[parentIndex]
        var childIndex = 2 * parentIndex + 1
        while (childIndex < length){
            if(childIndex+1 < length && array[childIndex+1] < array[childIndex]){
                childIndex++
            }
            if(temp <= array[childIndex]){
                break
            }
            array[parentIndex] = array[childIndex]
            parentIndex = childIndex
            childIndex = 2 * childIndex + 1
        }
        array[parentIndex] = temp
    }

    fun buildHeap(array: IntArray){
        for (i in (array.size-2)/2 downTo 0){
            downAdjust(array,i,array.size)
        }
    }
}
复制代码

测试:

fun testBinaryHeap(){
    var array = intArrayOf(1,2,3,4,5,6,7,8,9,0)
    BinaryHeap.upAdjust(array)
    println(array.contentToString())

    array = intArrayOf(7,1,3,10,5,2,8,9,6)
    BinaryHeap.buildHeap(array)
    println(array.contentToString())

}
复制代码

运行结果:

[0, 1, 3, 4, 2, 6, 7, 8, 9, 5]
[1, 5, 2, 6, 7, 3, 8, 9, 10]
复制代码

5.什么是优先队列?

上面介绍了队列的先进先出(FIFO)特性,而优先队列严格意义上来讲并不是队列,因为优先队列有自己的出队顺序,而且还有有两种情况:

  • 最大优先队列——当前最大的元素优先出队
  • 最小优先队列——当前最小的元素优先出队

代码实现:

/**
 * <p>文件描述:优先队列的实现<p>
 * <p>@author 烤鱼<p>
 * <p>@date 2019/10/31 0027 <p>
 * <p>@update 2019/10/31 0027<p>
 * <p>版本号:1<p>
 *
 */
class PriorityQueue {
    // 默认长度
    private var array = IntArray(16)
    private var size = 0

    // 入队
    fun enQueue(value: Int) {
        // 判断是否需要扩容
        if (size >= array.size) {
            reSize()
        }
        array[size++] = value
        upAdjust()
    }

    // 出队
    fun deQueue(): Int {
        if (size == 0) {
            throw Exception("the array is empty")
        }
        // 获取对顶元素
        val first = array.first()
        // 最后一个元素移到堆顶
        array[0] = array[--size]
        downAdjust()
        return first
    }

    // 队列扩容
    private fun reSize() {
        this.array = array.copyOf(2 * size)
    }

    // “上浮”调整
    private fun upAdjust() {
        var childIndex = size - 1
        var parentIndex = (childIndex - 1) / 2
        // 临时保存
        val temp = array[childIndex]
        while (childIndex > 0 && temp > array[parentIndex]) {
            // 赋值
            array[childIndex] = array[parentIndex]
            childIndex = parentIndex
            parentIndex /= 2
        }
        array[childIndex] = temp
    }

    // “下沉”调整
    private fun downAdjust() {
        var parentIndex = 0
        // 保存根节点的值
        val temp = array.first()
        var childIndex = 1
        while (childIndex < size) {
            // 如果有右孩子,且右孩子大于左孩子的值,则定位到右孩子
            if (childIndex + 1 < size && array[childIndex + 1] > array[childIndex]) {
                childIndex++
            }
            // 如果父节点大于子节点的值,跳出循环
            if (temp >= array[childIndex]) {
                break
            }
            // 赋值
            array[parentIndex] = array[childIndex]
            parentIndex = childIndex
            childIndex = 2 * childIndex + 1
        }
        array[parentIndex] = temp
    }
}
复制代码

测试:

fun testPriorityQueue(){
    val priorityQueue = PriorityQueue()
    priorityQueue.enQueue(3)
    priorityQueue.enQueue(5)
    priorityQueue.enQueue(10)
    priorityQueue.enQueue(2)
    priorityQueue.enQueue(7)
    println(priorityQueue.deQueue())
    println(priorityQueue.deQueue())
}
复制代码

运行结果:

10
7
复制代码

后记

1----本文由苏灿烤鱼整理编写,转载请注明

2----如果有什么想要交流的,欢迎留言。也可以加微信:Vicent_0310

3----个人能力有限,如有不正之处欢迎大家批评指证,必定虚心改正

传送门

关注下面的标签,发现更多相似文章
评论