树（下）

Posted on   |   In   |  

一.堆（Heap）

1.优先队列（Priority Quene）：特殊的“队列”，取出元素的顺序是按照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序。

  • 若采用数组或链表实现优先队列，
    • 数组：
      • 插入–元素总是插入尾部 — O(1)
      • 查找–查找关键字— O(n)
      • 删除–从数组中删除元素，需要将删除元素后的xx元素往前挪动–O(n)
    • 链表：
      • 插入–插在链表头部位置—O(1)
      • 删除–查找关键字 — O(n)
      • 删除–只需将指针改写即可–O(1)
  • 采用完全二叉树表示，满足以下两个条件：
    • 结构性：是完全二叉树（用数组存储）
    • 有序性：任一结点的关键字是其子树所有结点的最大值（或最小值）
      • 最大堆（MaxHeap）：最大值
      • 最小堆（MinHeap）：最小值
        从根节点到任一结点的路径具有有序性
    • 插入 O(logN)（参见网易云课堂数据结构陈越mooc）先将元素放入数组最后一位，然后再与其父结点比较，根据大小互换位置
    • 删除 O(logN) 删除最大元素，空出的位置由最后一个元素替补，然后最后一个元素与其他元素比较，小则互换位置，直到满足最大堆条件位置（以最大堆做解释，最小堆同理）
  • 最大堆的建立（后面堆排序就是建立在最大堆的基础上）
    • 方法1：通过插入操作，将N个元素一个个插入初始为空的堆里去，时间代价是O(NlogN)，每插入一个元素复杂度是O(logN)，所以插入N个就是O(NlogN)。
    • 方法2：在线性时间复杂度下建立最大堆（O(N)）
      • 将N个元素按输入顺序（这里的顺序不是大小顺序，只是按照位置顺序（1，2，3，4···）存入数组而已）存入，先满足完全二叉树的结构特性
      • 调整各结点位置，以满足最大堆的有序特性。（自底向上，使任一结点的左右子树都是一个堆）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
//最小堆的实现（创建，插入，删除，查找路径）
#include<iostream>
#include<vector>
using namespace std;

const int MAX_SIZE = 1001;
const int MIN_DATA = -100001;    //set sentinel
struct Heap
{
    int *heapArray;     //create dynamic array to storage element of heap
    int size;           //the size of current heap
    int capacity;       //the max size of heap

};

class MinHeap
{
public:
    MinHeap();
    ~MinHeap(){}
    Heap *CreateMinHeap(int maxSize);
    bool IsFull();
    bool IsEmpty();
    void InsertValMinHeap(int val,Heap *&MH);
    void Insert(int val);
    int DeleteMaxValMinHeap(Heap *&MH);
    int Delete();
    int FindVal(int position, vector<int> &ans);
private:
    Heap *m_h;
};
MinHeap::MinHeap()
{
    m_h = CreateMinHeap(MAX_SIZE);
}

Heap *MinHeap::CreateMinHeap(int maxSize)
{
    Heap *tempH = new Heap;
    tempH->heapArray = new int [maxSize];
    tempH->size = 0;
    tempH->capacity = maxSize;
    tempH->heapArray[0] = MIN_DATA;
    return tempH;
}

bool MinHeap::IsFull()
{
    if(m_h->size == m_h->capacity - 1)
    {
        return true;
    }
    return false;
}

bool MinHeap::IsEmpty()
{
    if(m_h->size == 0)
    {
        return true;
    }
    return false;
}

void MinHeap::Insert(int val)
{
    InsertValMinHeap(val, m_h);
}

void MinHeap::InsertValMinHeap(int val, Heap *&MH)
{
    if(IsFull())
    {
        cout << "heap is full " << endl;
        return;
    }
    int i = ++MH->size;
    for(; val < MH->heapArray[i/2]; i /= 2)
    {
        MH->heapArray[i] = MH->heapArray[i/2];
    }
    MH->heapArray[i] = val;
}

int MinHeap::DeleteMaxValMinHeap(Heap *&MH)
{
    if(IsEmpty())
    {
        cout << "heap is empty " << endl;
        return -1;
    }
    int maxData = MH->heapArray[1];
    int tempVal = MH->heapArray[MH->size--];
    int parent = 1, child = 0;
    for(; parent * 2 <= MH->size; parent = child)
    {
        child = parent * 2;
        if((child != MH->size) && (MH->heapArray[child + 1] < MH->heapArray[child]))
        {
            ++child;
        }
        if(tempVal <= MH->heapArray[child])
        {
            break;
        }
        MH->heapArray[parent] = MH->heapArray[child];
    }
    MH->heapArray[parent] = tempVal;
    return maxData;
}

int MinHeap::Delete()
{
   return DeleteMaxValMinHeap(m_h);
}
int MinHeap::FindVal(int position, vector<int> &ans)
{
    if(position < 0 || position > m_h->size)
    {
        cout << "can't find element " << endl;
    }
    else
    {
        for(int i = position; i > 0; i /= 2)
        {
            ans.push_back(m_h->heapArray[i]);
        }
    }
}

int main()
{
    int M = 0, N = 0;
    cin >> M >> N;
 //   vector<int> seqValVec;
    MinHeap mh;
    for(int i = 0; i < M; ++i)
    {
        int val = 0;
        cin >> val;
 //       seqValVec.push_back(val);
        mh.Insert(val);

    }
    mh.Delete();
    for(int i = 0; i < N; ++i)
    {
        int index = 0;
        cin >> index;
        vector<int> ans;
        mh.FindVal(index,ans);
        for(int i = 0; i < ans.size(); ++i)
        {
            cout << ans[i] << (i == ans.size() - 1 ? "\n":" ");
        }
    }
}

二.哈夫曼树和哈夫曼编码

  • 带权路径长度（WPL，Weight Path Length）：设二叉树有n个叶子结点，每个叶子结点带有权值Wk，从根节点到每个叶子结点的长度为Lk，则每个叶子结点的WPL之和：WPL = W0*L0 + ?? + Wi*Li +??+ Wn*Ln（i = 0???N）
  • 哈夫曼树（最优二叉树）：WPL最小的二叉树

  • 哈夫曼树的构造：每次将权值最小的两棵二叉树合并。
    例如：1 2 3 4 5
    构造如下：
    1 2合并得3，在3 3 4 5中选择最小的，3 3合并得 6 4 5，在其中选择最小的4 5 得6 9合并得15

    • 代码实现中，如何选取最小的两个元素，排序不如最小堆效率高，因为每次排完序，还要将合并后的元素放入序列中重新排序。构造最小堆，每次删除最小堆中的两个元素，然后插入合并后的元素，最终构造哈夫曼树的时间复杂度为O(NlogN)

  • 哈夫曼树的特点

    • 没有度为1的结点
    • 如果有N个叶子结点，哈夫曼树则共有2*N-1个结点
    • 哈夫曼树的任一非叶节点的左右子树交换后仍是哈夫曼树
    • 对同一组权值｛W1，W2，W3???Wn｝是否存在不同构的两棵哈夫曼树呢？（存在）
      例如｛1，2，3，3}就存在。（见MOOC课件）
  • 哈夫曼编码
    • 不等长编码，频率出现高的编码长度短一点，频率出现低的编码长度高一点。
      但是这样会出现二义性，例如：
      a:1,e:0,s:10,t:11
      那么对于1011的解释就有不止一种，可以解释成st或者aet，如何避免二义性？
    • 前缀码（prefix code）：任何字符的编码都不是另一字符的编码的前缀。
      上述例子中a的编码是t的编码的前缀，这样就造成了二义性。
    • 二叉树进行编码：
      （1）：左右分支：0，1（左为0，右为1）
      （2）：字符只在叶子结点上，不能出现在非叶子结点上
    • 给定一些字符的频率，根据频率先将哈夫曼树构造出来，给向左的边标记0，向右的标记1，这样所有的字符的哈夫曼编码就出来了，这样的二叉树查找代价也是最小的。

集合及运算

  • 并查集
    采用何种结构来存储集合，采用树来存储，所有结点均指向根节点，根节点代表该集合。然后用数组实现（链表也能实现）
下标 Data parent
0 1 -1
1 2 0
2 3 -1
3 4 0
4 5 2
5 6 -1
6 7 0
7 8 2
8 9 5
9 10 5

数据1的子节点有2，4，7
数据3的子节点有5，8
数据6的子节点有9，10
数据1，3，6分属三个不同的集合，因为他们的父结点为-1，在列表中没有，下标是元素在数组中的位置，这是在数组中存储的形式。