title: 数据结构
date: 2019-03-12 21:23:27
categories: 代码
__tags: 算法学习

数据结构

Heap - 堆

定义

一般情况下，堆通常指的是二叉堆，二叉堆是一个近似完全二叉树的数据结构，但由于对二叉树平衡及插入/删除操作较为麻烦，二叉堆实际上使用数组来实现。即物理结构为数组，逻辑结构为完全二叉树。子结点的键值或索引总是小于（或者大于）它的父节点，且每个节点的左右子树又是一个二叉堆(大根堆或者小根堆)。根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常被用作实现优先队列。

特点：

1.以数组表示，但是以完全二叉树的方式理解。
2.唯一能够同时最优地利用空间和时间的方法——最坏情况下也能保证使用 2N \log N2NlogN 次比较和恒定的额外空间。
3.在索引从0开始的数组中：

  • 父节点 i 的左子节点在位置(2*i+1)
  • 父节点 i 的右子节点在位置(2*i+2)
  • 子节点 i 的父节点在位置floor((i-1)/2)

基本操作

以大根堆为例，堆的常用操作如下。

  1. 最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点
  2. 创建最大堆：将堆所有数据重新排序
  3. 堆排序：移除位于第一个数据的根节点，并做最大堆调整的递归运算
    其中步骤1是给步骤2和3用的。
    {% asset_img 堆排序.gif 堆排序 %}

堆排序.gif

JAVA实现

  1. import java.util.*;
  2. /**
  3. *java实现大堆
  4. */
  5. public class MaxHeap {
  6.     private final int MAX_N = 10;
  7.     private final int[] heap = new int[MAX_N];
  8.     private int last = 0;
  10.     public int getLast() {
  11.         return last;
  12.     }
  14.     public void push(int x) {
  15.         int i = last++;
  16.         while (i > 0) {
  17.             int p = (i - 1) / 2;
  18.             if (heap[p] >= x) {
  19.                 break;
  20.             }
  21.             heap[i] = heap[p];
  22.             i = p;
  23.         }
  24.         heap[i] = x;
  25.     }
  27.     public int pop() {
  28.         int result = heap[0];
  29.         int x = heap[--last];
  30.         heap[last] = result;
  32.         int i = 0;
  33.         while (2 * i + 1 < last) {
  34.             int left = 2 * i + 1, right = 2 * i + 2, swap = left;
  35.             if (right < last && heap[left] < heap[right]) {
  36.                 swap = right;
  37.             }
  38.             if (heap[swap] <= x) {
  39.                 break;
  40.             }
  42.             heap[i] = heap[swap];
  43.             i = swap;
  44.         }
  45.         heap[i] = x;
  47.         return result;
  48.     }
  50.     @Override
  51.     public String toString() {
  52.         StringBuilder sb = new StringBuilder();
  53.         sb.append("maxHeap: [");
  54.         for (int i = 0; i < last - 1; i++) {
  55.             sb.append(String.format("%d, ", heap[i]));
  56.         }
  57.         if (last > 0) {
  58.             sb.append(heap[last - 1]);
  59.         }
  60.         sb.append("]");
  61.         return sb.toString();
  62.     }
  64.     public static void main(String[] args) {
  65.         MaxHeap maxHeap = new MaxHeap();
  67.         int[] array = new int[]{6, 5, 3, 1, 8, 7, 2, 4, 10, 9};
  68.         for (int i : array) {
  69.             maxHeap.push(i);
  70.             System.out.println(maxHeap);
  71.         }
  73.         for (int i = maxHeap.getLast() - 1; i >= 0; i--) {
  74.             System.out.println("pop max heap value: " + maxHeap.pop());
  75.             System.out.println(maxHeap);
  76.         }
  78.         PriorityQueue<Integer> pq = new PriorityQueue<Integer>(10, Collections.reverseOrder());
  79.         for (int i : array) {
  80.             pq.offer(i);
  81.             System.out.println(pq);
  82.         }
  84.         // Top K problem
  85.         int k = 5;
  86.         for (int i = 0; i < k; i++) {
  87.             Integer topk = pq.poll();
  88.             if (topk != null) {
  89.                 System.out.println("top " + (i + 1) + ": " + topk);
  90.             } else {
  91.                 System.out.println("poll null value!!!");
  92.             }
  93.         }
  94.     }
  95. }

栈

定义

栈是一种 LIFO(Last In First Out) 的数据结构，常用方法有添加元素，取栈顶元素，弹出栈顶元素，判断栈是否为空。
JAVA

  1. Deque<Integer> stack = new ArrayDeque<Integer>();
  2. s.size(); // size of stack

Methods

  • boolean isEmpty() - 判断栈是否为空，若使用 Stack 类构造则为 empty()
  • E peek() - 取栈顶元素，不移除
  • E pop() - 移除栈顶元素并返回该元素
  • E push(E item) - 向栈顶添加元素

栈实现

  1. public interface MyStack<Item> extends Iterable<Item> {
  3.     MyStack<Item> push(Item item);
  5.     Item pop() throws Exception;
  7.     boolean isEmpty();
  9.     int size();
  11. }

数组实现

  1. public class ArrayStack<Item> implements MyStack<Item> {
  3.     // 栈元素数组，只能通过转型来创建泛型数组
  4.     private Item[] a = (Item[]) new Object[1];
  6.     // 元素数量
  7.     private int N = 0;
  10.     @Override
  11.     public MyStack<Item> push(Item item) {
  12.         check();
  13.         a[N++] = item;
  14.         return this;
  15.     }
  18.     @Override
  19.     public Item pop() throws Exception {
  21.         if (isEmpty()) {
  22.             throw new Exception("stack is empty");
  23.         }
  25.         Item item = a[--N];
  27.         check();
  29.         // 避免对象游离
  30.         a[N] = null;
  32.         return item;
  33.     }
  36.     private void check() {
  38.         if (N >= a.length) {
  39.             resize(2 * a.length);
  41.         } else if (N > 0 && N <= a.length / 4) {
  42.             resize(a.length / 2);
  43.         }
  44.     }
  47.     /**
  48.      * 调整数组大小，使得栈具有伸缩性
  49.      */
  50.     private void resize(int size) {
  52.         Item[] tmp = (Item[]) new Object[size];
  54.         for (int i = 0; i < N; i++) {
  55.             tmp[i] = a[i];
  56.         }
  58.         a = tmp;
  59.     }
  62.     @Override
  63.     public boolean isEmpty() {
  64.         return N == 0;
  65.     }
  68.     @Override
  69.     public int size() {
  70.         return N;
  71.     }
  74.     @Override
  75.     public Iterator<Item> iterator() {
  77.         // 返回逆序遍历的迭代器
  78.         return new Iterator<Item>() {
  80.             private int i = N;
  82.             @Override
  83.             public boolean hasNext() {
  84.                 return i > 0;
  85.             }
  87.             @Override
  88.             public Item next() {
  89.                 return a[--i];
  90.             }
  91.         };
  93.     }
  94. }

表

链表实现

需要使用链表的头插法来实现，因为头插法中最后压入栈的元素在链表的开头，它的 next 指针指向前一个压入栈的元素，在弹出元素时就可以通过 next 指针遍历到前一个压入栈的元素从而让这个元素成为新的栈顶元素。

  1. public class ListStack<Item> implements MyStack<Item> {
  3.     private Node top = null;
  4.     private int N = 0;
  7.     private class Node {
  8.         Item item;
  9.         Node next;
  10.     }
  13.     @Override
  14.     public MyStack<Item> push(Item item) {
  16.         Node newTop = new Node();
  18.         newTop.item = item;
  19.         newTop.next = top;
  21.         top = newTop;
  23.         N++;
  25.         return this;
  26.     }
  29.     @Override
  30.     public Item pop() throws Exception {
  32.         if (isEmpty()) {
  33.             throw new Exception("stack is empty");
  34.         }
  36.         Item item = top.item;
  38.         top = top.next;
  39.         N--;
  41.         return item;
  42.     }
  45.     @Override
  46.     public boolean isEmpty() {
  47.         return N == 0;
  48.     }
  51.     @Override
  52.     public int size() {
  53.         return N;
  54.     }
  57.     @Override
  58.     public Iterator<Item> iterator() {
  60.         return new Iterator<Item>() {
  62.             private Node cur = top;
  65.             @Override
  66.             public boolean hasNext() {
  67.                 return cur != null;
  68.             }
  71.             @Override
  72.             public Item next() {
  73.                 Item item = cur.item;
  74.                 cur = cur.next;
  75.                 return item;
  76.             }
  77.         };
  79.     }
  80. }

队列

下面是队列的链表实现，需要维护 first 和 last 节点指针，分别指向队首和队尾。

这里需要考虑 first 和 last 指针哪个作为链表的开头。因为出队列操作需要让队首元素的下一个元素成为队首，所以需要容易获取下一个元素，而链表的头部节点的 next 指针指向下一个元素，因此可以让 first 指针链表的开头。

  1. public interface MyQueue<Item> extends Iterable<Item> {
  3.     int size();
  5.     boolean isEmpty();
  7.     MyQueue<Item> add(Item item);
  9.     Item remove() throws Exception;
  10. }
  1. public class ListQueue<Item> implements MyQueue<Item> {
  3.     private Node first;
  4.     private Node last;
  5.     int N = 0;
  8.     private class Node {
  9.         Item item;
  10.         Node next;
  11.     }
  14.     @Override
  15.     public boolean isEmpty() {
  16.         return N == 0;
  17.     }
  20.     @Override
  21.     public int size() {
  22.         return N;
  23.     }
  26.     @Override
  27.     public MyQueue<Item> add(Item item) {
  29.         Node newNode = new Node();
  30.         newNode.item = item;
  31.         newNode.next = null;
  33.         if (isEmpty()) {
  34.             last = newNode;
  35.             first = newNode;
  36.         } else {
  37.             last.next = newNode;
  38.             last = newNode;
  39.         }
  41.         N++;
  42.         return this;
  43.     }
  46.     @Override
  47.     public Item remove() throws Exception {
  49.         if (isEmpty()) {
  50.             throw new Exception("queue is empty");
  51.         }
  53.         Node node = first;
  54.         first = first.next;
  55.         N--;
  57.         if (isEmpty()) {
  58.             last = null;
  59.         }
  61.         return node.item;
  62.     }
  65.     @Override
  66.     public Iterator<Item> iterator() {
  68.         return new Iterator<Item>() {
  70.             Node cur = first;
  73.             @Override
  74.             public boolean hasNext() {
  75.                 return cur != null;
  76.             }
  79.             @Override
  80.             public Item next() {
  81.                 Item item = cur.item;
  82.                 cur = cur.next;
  83.                 return item;
  84.             }
  85.         };
  86.     }
  87. }

树

图

红黑树*