【每日一题】堆的任意位置的调整

题目描述

---

以插入的方式来建堆实际上是O(NlogN)，而O(N)的建堆方式就是向下调整算法完成的。
堆排序算法描述及时间复杂度分析

h的话就是heap堆，size就是当前存了多少个元素，指向下一个可以存放的位置。
ph存储的是插入的第k个数以及对应在h数组当中下标的映射;
hp存储的是堆里面的每一个点是第k个元素。

删除一个任意位置的元素，如果已经定位到该元素的位置，那么只需要swap（a[i],a[size]），然后将a[i]这个位置的元素进行向上或者向下调整，因为交换过后的元素可能比当前元素大也可能比当前元素小，但是走向上调整或者向下调整一遍就能得到答案。
修改的操作也是如此。直接修改当前元素，然后向上或者向下调整。

• n 就是一直在增大，ph数组不会往回头看，因为k是不断增大的。
• _size 就是最后一个元素
• ph的下标标识当前节点是第k个插入的元素，ph中的元素不会被覆盖，并且由于k是不断增大的，所以ph数组会一直往后走。
• hp数组是堆当中的元素到ph的映射，由于增删改，所以hp当中的元素就会一直发生变化（hp.size() == h.size()）。但只需要当前元素能够找到对应ph的下标即可，得知自己是第k个元素插入的即可。（这个是交换元素的需求，因为两个元素交换的时候也需要更改ph表,标识插入的次序的改变）。
  
  ph的下标就是第K+1个插入的元素，如0位置就是第一个。

每一次调整都是需要heap_swap，维护三个数组的关系。

题解

---

#include
using namespace std;
#include

const int N = 100010;
int h[N];
int hp[N];//heap -> p
int ph[N];//p -> heap
int _size = 0;//遍历到第几个元素
void heap_swap(int parent, int child)
{
    swap(ph[hp[parent]], ph[hp[child]]);
    swap(hp[parent], hp[child]);
    swap(h[parent], h[child]);
}

void AdjustUp(int child)//key标识元素
{
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        if (h[parent] > h[child])
        {
            heap_swap(parent, child);
            child = parent;
            parent = (child - 1) / 2;
        }
        else break;
    }

}
//小堆
void AdjustDown(int parent)
{
    int child = parent * 2 + 1;
    while (child < _size)
    {
        if (child + 1 < _size && h[child] > h[child + 1])
        {
            child++;
        }
        if (h[parent] > h[child])
        {
            heap_swap(parent, child);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
int main()
{
    int m;
    cin >> m;
    int n = 0;
    while (m--)
    {
        string str;
        cin >> str;
        if (str == "I")
        {
            int k;
            cin >> k;
            int child = _size;
            h[child] = k;
            ph[n] = _size;
            hp[_size] = n;
            AdjustUp(_size);
            ++_size;
            ++ n;
        }
        else if (str == "PM")
        {
            cout << h[0] << endl;
        }
        else if (str == "DM")
        {
            heap_swap(0,_size - 1);
            _size--;
            AdjustDown(0);
        }
        else if (str == "D")
        {
            int k;
            cin >> k;
            k = ph[k - 1];
            heap_swap(k, _size - 1);
            --_size;
            AdjustUp(k);
            AdjustDown(k);
        }
        else
        {
            int k, x;
            cin >> k >> x;
            k = ph[k - 1];
            h[k] = x;
            AdjustDown(k);
            AdjustUp(k);
        }
    }
    return 0;
}
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

---

end

• 喜欢就收藏
• 认同就点赞
• 支持就关注
• 疑问就评论