1
class Heap:
2
    def __init__(self):
3
        self.q = []
4

5
    def push(self, data):
6
        i = len(self.q)
7
        self.q.append(data)
8
        while i > 0:
9
            if self.q[i] > self.q[(i - 1) // 2]:
10
                self.q[i], self.q[(i - 1) // 2] = self.q[(i - 1) // 2], self.q[i]
11
                i = (i - 1) // 2
12
            else:
13
                return
14

15
    def pop(self):
16
        if len(self.q) == 0:
17
            return
18
        self.q[0] = self.q[-1]
19
        self.q.pop()
20

21
        def heapify(i):
22
            ind = i
23
            l = 2 * i + 1
24
            r = 2 * i + 2
25
            if r < len(self.q) and self.q[ind] < self.q[r]:
26
                ind = r
27
            if l < len(self.q) and self.q[ind] < self.q[l]:
28
                ind = l
29
            if ind != i:
30
                self.q[i], self.q[ind] = self.q[ind], self.q[i]
31
                heapify(ind)
32

33
        heapify(0)
34

35
    def top(self):
36
        return self.q[0]
37

38

39
class Solution:
40
    def wiggleSort(self, nums: List[int]) -> None:
41
        n = len(nums)
42
        h = Heap()
43
        for i in nums:
44
            h.push(i)
45
        for i in range(1, n, 2):
46
            nums[i] = h.top()
47
            h.pop()
48
        for i in range(0, n, 2):
49
            nums[i] = h.top()
50
            h.pop()