---
title: '二元樹 - HashMap & Heap'
disqus: kyleAlien
---

二元樹 - HashMap & Heap
===

## OverView of Content

[TOC]

## 二元樹拓展

**透過二元樹可以來製作 其他類型的 數據結構**

## 二元樹 HashMap

使用二元樹完成 HashMap，其中需要修改的主要就是 Node 節點，**Node 要同時儲存 Key/Value 數據**，其餘操作與二原樹相同

public static final class HashMapTreeNode<V> {
    // Key/Value 數據
    private final int key;
    private V value;

    // 左右子樹
    public HashMapTreeNode<V> left, right;

    public HashMapTreeNode(int key, V value) {
        this.key = key;
        this.value = value;
    }
}

### 二元樹 HashMap - 基礎操作

* 其中操作需要改名，與 HashMap 操作相同名稱，以下舉例兩種

| 二元樹函數 | 修改 Map 使用的函數名稱 |
| - | - |
| `insert(k, v)` | `put(k, v)` |
| `get(k)` | `get(k)` |

1. `insert(k, v)` 操作改為 `put(k, v)`

        private final HashMapTreeNode<V> header;

        public HashMapTree(HashMapTreeNode<V> header) {
            this.header = header;
        }

        public HashMapTreeNode<V> put(int key, V val) {
            _put(header, key, val);
            return header;
        }

        private HashMapTreeNode<V> _put(HashMapTreeNode<V> root, int key, V val) {
            if(root == null) {
                return new HashMapTreeNode<>(key, val);
            }

            if(root.key >= key) {
                root.left = _put(root.left, key, val);
            } else if (root.key < key) {
                root.right = _put(root.right, key, val);
            }

            return root;
        }

2. 取操作改為 `get(k)` (並沒有移除操作)

        public V get(int key) {
            // 使用呼叫函數 _get
            HashMapTreeNode<V> result = _get(header, key);

            return result == null ? null : result.value;
        }

        public HashMapTreeNode<V> _get(HashMapTreeNode<V> root, int key) {
            if(root == null) {
                return null;
            }

            if(root.key == key) {
                return root;
            }

            if(root.key >= key) {
                return _get(root.left, key);
            } else if(root.key < key) {
                return _get(root.right, key);
            }

            return null;
        }

* 測試：二元樹的剩餘操作其實都沒變，主要要調整 Node

    public static void main(String[] args) {
        HashMapTreeNode<String> root = new HashMapTreeNode<>(53, "Apple");

        HashMapTree<String> tree = new HashMapTree<>(root);

        tree.put(76, "Banana");

        String result = tree.get(76);
        System.out.println("Result: " + result);
    }

> 

### 二元樹 HashMap - 尋訪

* 使用二元樹的 HashMap 可以使用 **中序走訪** 來達到 **升序結果**，這是跟 HashMap 不同的地方 (二元樹的特性)

    // 中序走訪

    public void inorder() {
        _inorder(header);
    }

    private void _inorder(HashMapTreeNode<V> root) {
        if(root == null) {
            return;
        }
        _inorder(root.left);

        System.out.println("key: " + root.key + ", value: " + root.value);

        _inorder(root.right);
    }

* 測試：中序走訪二元樹，確實可以得到一個升序結果

        public static void main(String[] args) {
            HashMapTreeNode<String> root = new HashMapTreeNode<>(53, "C");

            HashMapTree<String> tree = new HashMapTree<>(root);

            tree.put(5, "A");
            tree.put(20, "B");
            tree.put(58, "D");
            tree.put(76, "E");
            tree.put(79, "F");

            tree.inorder();
        }

> 

## 二元樹 Heap

使用二元樹完成 Heap，其中需要修改的主要就是 Node 節點，**Node 要同時儲存 Priority/Value 數據** (Key 換成 Priority)，其餘操作與二原樹相同

public static final class HeapTreeNode<V> {
    private final int priority;
    private V value;

    public HeapTreeNode<V> left, right;

    public HeapTreeNode(int priority, V value) {
        this.priority = priority;
        this.value = value;
    }
}

:::success
* Node 擺放規則，要使用 Heap 還是二元樹 ?

**使用二元樹規則** ! 使用二元樹完成的 Heap 的排序規則還是與二元樹的排序規則相同，好處是可以無線拓展二元樹大小 (原本使用 Array 會有數量上限問題)
:::

### 二元樹 Heap - 基礎操作

* 其中操作需要改名，與 Heap 操作相同名稱，以下舉例兩種

| 二元樹函數 | 修改 Map 使用的函數名稱 |
| - | - |
| `insert(k, v)` | `enqueue(k, v)` |
| `remove(k)` | `dequeue()` |

1. `insert(k, v)` 操作改為 `enqueue(k, v)`：在原本的 Heap 結構中　`enqueue` 操作需要 swim(上浮) 操作；

**二元樹的 Heap 就 ++不需要 swim(上浮) 操作++**

        private int count;
        private HeapTreeNode<V> header;

        public HeapTree(HeapTreeNode<V> header) {
            this.count = 0;
            this.header = header;
        }

        public void enqueue(int priority, V val) {
            _enqueue(header, priority, val);
            count += 1;
        }

        // 輔助函數
        private HeapTreeNode<V> _enqueue(HeapTreeNode<V> root, int priority, V val) {
            if(root == null) {
                return new HeapTreeNode<>(priority, val);
            }

            if(root.priority >= priority) {
                root.left = _enqueue(root.left, priority, val);
            } else if (root.priority < priority) {
                root.right = _enqueue(root.right, priority, val);
            }

            return root;
        }

2. `remove(k)` 操作改為 `dequeue()`：**原本 Heap 結構中　`dequeue` 操作會取陣列頂端的節點，該節點是最高的優先度**

**所以二元樹的 Heap 就需要 ++刪除最大值、取得最大值 的輔助函數++**

:::success
* **取最大值 - 效率**

Heap 的原本特性可以找到以 O(1) 的效率來找到最大值 (`在 array[1]`)；**使用二元樹的 Heap，最大值在最右下方，可以用 `log(N)` 的速度找到最大值**
:::

        public HeapTreeNode<V> dequeue() {
            // 取最大值
            HeapTreeNode<V> max = _getMax(header);
            
            // 在移除的過程中可能移除的是 Header，所以要更新 Header
            header = _removeMax(header);
            count -= 1;
            return max;
        }

        private HeapTreeNode<V> _getMax(HeapTreeNode<V> root) {
            if(root.right == null) {
                // 沒有右子樹就返回自身 (自身最大
                return root;
            }

            // 最大值會在節點右邊
            return _getMax(root.right);
        }

        private HeapTreeNode<V> _removeMax(HeapTreeNode<V> root) {
            // 找最大值
            if(root.right == null) {
                return root.left;    // 可能還有左子樹，所以需要返回左子樹串接
            }

            root.right = _removeMax(root.right);

            return root;
        }

* 測試：可以看到結果如同最大 Heap 結構，從 Priority 最高開始 `dequeue`

    public static void main(String[] args) {
        HeapTree<String> heapTree = new HeapTree<>(new HeapTreeNode<>(9, "F"));

        heapTree.enqueue(5, "B");
        heapTree.enqueue(2, "He");
        heapTree.enqueue(8, "O");

        heapTree.enqueue(12, "Mg");
        heapTree.enqueue(10, "Ne");
        heapTree.enqueue(14, "Si");

        int c = heapTree.count;
        for(int i = 0; i < c; i++) {
            HeapTreeNode<String> node = heapTree.dequeue();
            System.out.println("priority: " + node.priority + ", val:" + node.value);
        }

    }

> 

:::warning
* 二元樹 Heap 的效能比原來 Heap 結構還要差一點
:::

## Appendix & FAQ

:::info
:::

###### tags: `資料結構`