# Heap

###### tags: `LeetCode筆記`

### Priority Queues

In a priority queue, an element with high priority is served before an element with low priority.

A priority queue is an abstract data type, while a Heap is a data structure.
A Heap is not a Priority Queue, but a way to implement a Priority Queue.

Array和Link List實作Priorty Queues只會在insertion或deletion其中一個是O(1)另一個是O(N)
Heap實作Priorty Queues則是insertion或deletion兩個都O(logN)

## :memo: 一、基本定義
* Is a complete binary tree
* The value of each node must be no greater than (or no less than) the value of its child nodes

## :memo: 二、特性
* Insertion of an element into the Heap has a time complexity of O(logN)
* Deletion of an element from the Heap has a time complexity of O(logN)
* The maximum/minimum value in the Heap can be obtained with O(1) time complexity


## :memo: 三、Implementation

利用陣列去實作Heap，陣列的大小等於Heap的節點個數加1，因為陣列第0元素存的是Heap的節點個數(size)，陣列第1元素才開始放Heap的節點


If the tree **root is at index 0**, with **valid indices 0 through n − 1**, then each element at index i has
* children at indices 2i + 1 and 2i + 2
* its parent at index floor((i − 1) / 2).

**Alternatively**, if the tree **root is at index 1**, with **valid indices 1 through n**, then each element at index i has
* children at indices 2i and 2i +1
* its parent at index floor(i / 2).

## :memo: Min Heap C
### 結構

#define heapSize 3

typedef struct {
    int heap[heapSize + 1];
    int size;
} myHeap;

### Initialization

myHeap* minH = (myHeap*) malloc(sizeof(myHeap));
minH->heap[0] = 0;
minH->size = 0;

### 插入

void add(myHeap* obj, int val)
{
    obj->size++;

    if (obj->size > heapSize)
    {
        printf("Added too many elements!\n");
        obj->size--;
        return;
    }

    obj->heap[obj->size] = val;

    int index = obj->size;
    int parent = index / 2;
    while (obj->heap[index] < obj->heap[parent] && index > 1)  //小於
    {
        int temp = obj->heap[index];
        obj->heap[index] = obj->heap[parent];
        obj->heap[parent] = temp;
        index = parent;
        parent = index / 2;
    }	
}

### 取出第一項

int pop(myHeap* obj)
{
    if (obj->size < 1)
    {
        printf("Don't have any element!\n");
        return INT_MAX;
    }
    else
    {
        int removeElement = obj->heap[1];
        obj->heap[1] = obj->heap[obj->size];
        obj->size--;
        int index = 1;
        while (index <= obj->size / 2)  //是小於等於 
        {
            int left = index * 2;
            int right = index * 2 + 1;
            if (obj->heap[index] > obj->heap[left] || obj->heap[index] > obj->heap[right])  //大於
            {
                if (obj->heap[left] < obj->heap[right])
                {
                    int temp = obj->heap[left];
                    obj->heap[left] = obj->heap[index];
                    obj->heap[index] = temp;
                    index = left;
                }
                else
                {
                    int temp = obj->heap[right];
                    obj->heap[right] = obj->heap[index];
                    obj->heap[index] = temp;
                    index = right;
                }				
            }
            else
            {
                break;
            }
        } 
        return removeElement;
    }
}

### 回傳root值

int peek(myHeap* obj)
{
    return obj->heap[1];
}

## :memo: Max Heap C

### 結構

#define heapSize 5

typedef struct {
    int heap[heapSize+1];
    int size;
} myHeap;

### Initialization

myHeap* maxH = (myHeap*) malloc(sizeof(myHeap));
maxH->heap[0] = 0;
maxH->size = 0;

### 插入

void add(myHeap* obj, int val)
{
    obj->size++;

    if (obj->size > heapSize)
    {
        printf("Added too many elements!\n");
        obj->size--;
        return;
    }

    obj->heap[obj->size] = val;

    int index = obj->size;
    int parent = index / 2;
    while (obj->heap[index] > obj->heap[parent] && index > 1)  //大於
    {
        int temp = obj->heap[index];
        obj->heap[index] = obj->heap[parent];
        obj->heap[parent] = temp;
        index = parent;
        parent = index / 2;
    }	
}

### 取出第一項

int pop(myHeap* obj)
{
    if (obj->size < 1)
    {
        printf("Don't have any element!\n");
        return INT_MAX;
    }
    else
    {
        int removeElement = obj->heap[1];
        obj->heap[1] = obj->heap[obj->size];
        obj->size--;
        int index = 1;
        while (index <= obj->size/2)  //是小於等於 
        {
            int left = index * 2;
            int right = index * 2 + 1;
            if(obj->heap[index] < obj->heap[left] || obj->heap[index] < obj->heap[right])  //小於
            {
                if(obj->heap[left] > obj->heap[right])
                {
                    int temp = obj->heap[left];
                    obj->heap[left] = obj->heap[index];
                    obj->heap[index] = temp;
                    index = left;
                }
                else
                {
                    int temp = obj->heap[right];
                    obj->heap[right] = obj->heap[index];
                    obj->heap[index] = temp;
                    index = right;
                }				
            }
            else
            {
                break;
            }
        } 
        return removeElement;
    }
}

### 回傳root值

int peek(myHeap* obj)
{
    return obj->heap[1];
}

## :memo: Min Heap C++
1. priority_queue<int, vector<int\>, greater<int\>> pq;
2. multiset<int\> mset;

## :memo: Max Heap C++
1. priority_queue<int\> pq(nums.begin(), nums.end());
2. multiset<int, greater<int\>> mset(nums.begin(), nums.end());

// make heap 要指定成pair<int, string>類型, 不然原本是vector<int>
make_heap(begin(vt), end(vt),  greater<pair<int, string>>());  
// pop heap 要指定成pair<int, string>類型, 不然原本是vector<int>
pop_heap(vt.begin(), vt.end(), greater<pair<int, string>>());  

## :memo: 三、Construct a Heap C
### function

int min(int* nums, int l, int r) {       
    if (r > nums[0])
    {  
        return l;
    }
    
    if (nums[l] <= nums[r])
    {
        return l;
    }
    else
    {
        return r;
    }
}

int max(int* nums, int l, int r) {       
    if (r > nums[0])
    {  
        return l;
    }
    
    if (nums[l] >= nums[r])
    {
        return l;
    }
    else
    {
        return r;
    }
}

void swap(int* nums, int i, int j) {
    int temp = 0;
    temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

### Min Heap
#### 主程式

int* heap = (int*) malloc(sizeof(int) * (numsSize + 1));
heap[0] = numsSize;
for (int i = 1; i < numsSize + 1; i++)
{
    heap[i] = nums[i - 1];
}
Heapify(heap, heap[0]);

#### Heapify

void Heapify(int* nums, int size) {
    int n = size;
    
    for (int i = n / 2; i > 0; i--)
    {
        int r = i;
        while (2 * r <= n)
        {
            int m = min(nums, 2 * r, 2 * r + 1);
            if (nums[r] > nums[m])
            {
                swap(nums, r, m);
                r = m;
            }
            else
            {
                break;
            }
        }
    }
}

### Max Heap
#### 主程式

int* heap = (int*) malloc(sizeof(int) * (numsSize + 1));
heap[0] = numsSize;
for (int i = 1; i < numsSize + 1; i++)
{
    heap[i] = nums[i - 1];
}
Heapify(heap, heap[0]);

#### Heapify

void Heapify(int* nums, int size){
    int n = size;
    
    for (int i = n / 2; i > 0; i--)
    {
        int r = i;
        while (2 * r <= n)
        {
            int m = max(nums, 2 * r, 2 * r + 1);
            if (nums[r] < nums[m])
            {
                swap(nums, r, m);
                r = m;
            }
            else
            {
                break;
            }
        }        
    }
}

## :memo: 四、Space and Time Complexity

## :memo: Last Stone Weight (Easy)
You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:

* If x == y, both stones are destroyed, and
* If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.
At the end of the game, there is at most one stone left.

Return the weight of the last remaining stone. If there are no stones left, return 0.


### 作法 Max Heap
**時間: O(NlogN)**

用max-heap，C++的priority_queue當size=0時pq.top()還會吐出值來，要用if檢查size=0時return 0才正確

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> pq(stones.begin(), stones.end());
        
        while (pq.size() > 1) {
            int x = pq.top();
            pq.pop();
            int y = pq.top();
            pq.pop();
            int diff = x - y;
            if (diff > 0) {
                pq.push(diff);
            }
        }
        
        if (pq.size() == 1) {
            return pq.top();    
        }
        else {
            return 0;
        }
    }
};

### 作法 bucket sort Java
**時間: O(N+W)**

class Solution {
    
    public int lastStoneWeight(int[] stones) {
        
        // Set up the bucket array.
        int maxWeight = stones[0];
        for (int stone: stones) {
            maxWeight = Math.max(maxWeight, stone);
        }
        int[] buckets = new int[maxWeight + 1];

        // Bucket sort.
        for (int weight : stones) {
            buckets[weight]++;
        }

        // Scan through the buckets.
        int biggestWeight = 0;
        int currentWeight = maxWeight;
        while (currentWeight > 0) {
            if (buckets[currentWeight] == 0) {
                currentWeight--;
            } else if (biggestWeight == 0) {
                buckets[currentWeight] %= 2;
                if (buckets[currentWeight] == 1) {
                    biggestWeight = currentWeight;
                }
                currentWeight--;
            } else {
                buckets[currentWeight]--;
                if (biggestWeight - currentWeight <= currentWeight) {
                    buckets[biggestWeight - currentWeight]++;
                    biggestWeight = 0;
                } else {
                    biggestWeight -= currentWeight;
                }
            }
        }
        return biggestWeight;
    }
}

## :memo: *The K Weakest Rows in a Matrix (Easy)
You are given an m x n binary matrix mat of 1's (representing soldiers) and 0's (representing civilians). The soldiers are positioned in front of the civilians. That is, all the 1's will appear to the left of all the 0's in each row.

A row i is weaker than a row j if one of the following is true:

* The number of soldiers in row i is less than the number of soldiers in row j.
* Both rows have the same number of soldiers and i < j.

Return the indices of the k weakest rows in the matrix ordered from weakest to strongest.


### 作法 Linear Search and Sorting
**時間: O(m⋅(n+logm))**
建立(soliders,index)的pair一起去sorting若soliders相同就比index

### 作法 Linear Search and Map
**時間: O(m⋅(n+logm))**



### 作法 Binary Search and Sorting/ Map
**時間: O(m⋅logmn)**
利用二元搜尋找士兵數量
接著套作法2

### 作法 Binary Search and Priority Queue C++
**時間: O(m⋅lognk)**

class Solution {
public:
    int binarysearch(vector<int> m) {
        int l = 0;
        int h = m.size() - 1;
        while (l <= h) {
            int mid = l + (h - l) / 2;
            if (m[mid] == 0) {
                h = mid - 1;
            }
            else {
                l = mid + 1;
            }
        }
        
        return l;
    }
    //  max-heap
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        priority_queue<pair<int, int>> pq;
        vector<int> ans;
        
        for (int i = 0; i < mat.size(); i++) {
            int cnt = binarysearch(mat[i]);
            pq.push(make_pair(cnt, i));
            
            if (pq.size() > k) {
                pq.pop();
            }
        }
        
        for (int i = 0; i < k; i++) {
            ans.push_back(pq.top().second);
            pq.pop();
        }
        
        reverse(ans.begin(), ans.end());
        
        return ans;
    }
};

### 作法 Vertical Iteration O(m⋅n)
**時間: O(m⋅n)**
垂直去看，看到0的左邊是1代表結束數士兵數量，越先看到的index代表士兵數量越少，index越前面，好聰明

## :memo: Kth Largest Element in a Stream (Easy)
Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.


### 作法
在建立結構時新增一個k當作size要維持前k個中最小(等同於全部第k個大)的minHeap，接著在建立minHeap時，取前k個大的數字當minHeap，而在新增時先判斷pq的size，超過k時pq.pop()後pq.top()成為第K大的數字

class KthLargest {  // min-heap using priority_queue
public:
    int K;
    priority_queue<int, vector<int>, greater<int>> pq;
    KthLargest(int k, vector<int>& nums) {
        K = k;
        for (int i = 0; i < nums.size(); i++) {
            pq.push(nums[i]);
            if (pq.size() > k) {
                pq.pop();
            }
        }
        
    }
    
    int add(int val) {
        pq.push(val);
        if (pq.size() > K) {
            pq.pop();
        }
        
        return pq.top();
    }
};

## :memo: Kth Largest Element in an Array (Medium)
Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

### 作法 C++
This problem needs to use partial sorting. **In STL**, there are two built-in functions (**nth_element** and **partial_sort**) for this.

#### nth_element

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        nth_element(nums.begin(), nums.begin() + k - 1, nums.end(), greater<int>());
        return nums[k - 1];
    }
};

#### partial_sort

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        partial_sort(nums.begin(), nums.begin() + k, nums.end(), greater<int>());
        return nums[k - 1];
    }
};

Note the off-by-1 difference in the second argument of the two built-in functions.

We may also use a heap to solve this problem. We can maintain the largest **k** elements in a heap with the smallest among them at the top. Or we can add all the elements to a heap, with the largest at the top, and then pop the heap for **k - 1** times, then the one on the top is our target. The first one is min-heap and the second one is max-heap. **In STL**, both **priority_queue** and **multiset** can be used as a min/max-heap.

#### min-heap using priority_queue

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for (int num : nums) {
            pq.push(num);
            if (pq.size() > k) {
                pq.pop();
            }
        }
        return pq.top();
    }
};

#### max-heap using priority_queue

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq(nums.begin(), nums.end());
        for (int i = 0; i < k - 1; i++) {
            pq.pop();
        }
        return pq.top();
    }
};

#### min-heap using multiset

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        multiset<int> mset;
        for (int num : nums) {
            mset.insert(num);
            if (mset.size() > k) {
                mset.erase(mset.begin());
            }
        }
        return *mset.begin();
    }
};

#### max-heap using multiset

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        multiset<int, greater<int>> mset(nums.begin(), nums.end());
        for (int i = 0; i < k - 1; i++) {
            mset.erase(mset.begin());
        }
        return *mset.begin();
    }
};

#### Partition
The partition subroutine of quicksort can also be used to solve this problem. In partition, we divide the array into

elements>=pivot pivot elements<=pivot

Then, according to the index of pivot, we will know whther the kth largest element is to the left or right of pivot or just itself.

In average, this algorithm reduces the size of the problem by approximately one half after each partition, giving the recurrence T(n) = T(n/2) + O(n) with O(n) being the time for partition. The solution is T(n) = O(n), which means we have found an average linear-time solution. However, in the worst case, the recurrence will become T(n) = T(n - 1) + O(n) and T(n) = O(n^2).

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int left = 0, right = nums.size() - 1, kth;
        while (true) {
            int idx = partition(nums, left, right);
            if (idx == k - 1) {
                kth = nums[idx];
                break;
            }
            if (idx < k - 1) {
                left = idx + 1;
            } else {
                right = idx - 1;
            }
        }
        return kth;
    }
private:
    int partition(vector<int>& nums, int left, int right) {
        int pivot = nums[left], l = left + 1, r = right;
        while (l <= r) {
            if (nums[l] < pivot && nums[r] > pivot) {
                swap(nums[l++], nums[r--]);
            }
            if (nums[l] >= pivot) {
                l++;
            }
            if (nums[r] <= pivot) {
                r--;
            }
        }
        swap(nums[left], nums[r]);
        return r;
    }
};

#### Heapsort
In the above we have presented heap solutions using STL. You may also implement your own heap if you are interested. I suggest you to read the Heapsort chapter of Introduction to Algorithms if you are not familiar with it. The following code implements a max-heap.

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        buildMaxHeap(nums);
        for (int i = 0; i < k - 1; i++) {
            swap(nums[0], nums[--heapSize]);
            maxHeapify(nums, 0);
        }
        return nums[0];
    }
private:
    int heapSize;
    
    int left(int i) {
        return (i << 1) + 1;
    }
    
    int right(int i) {
        return (i << 1) + 2;
    }
    
    void maxHeapify(vector<int>& nums, int i) {
        int largest = i, l = left(i), r = right(i);
        if (l < heapSize && nums[l] > nums[largest]) {
            largest = l;
        }
        if (r < heapSize && nums[r] > nums[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(nums[i], nums[largest]);
            maxHeapify(nums, largest);
        }
    }
    
    void buildMaxHeap(vector<int>& nums) {
        heapSize = nums.size();
        for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
            maxHeapify(nums, i);
        }
    }
};

### 作法 Sort
**時間: O(NlogN)**

### 作法 Heap
**時間: O(klogN)**

### 作法 Quickselect
**時間: O(N)**

class Solution {
public:
    int quickSelect(vector<int>& nums, int k) {
        int pivot = nums[rand() % nums.size()];

        vector<int> left;
        vector<int> mid;
        vector<int> right;

        for (int num : nums) {
            if (num > pivot) {
                left.push_back(num);
            }
            else if (num < pivot) {
                right.push_back(num);
            }
            else {
                mid.push_back(num);
            }
        }

        if (k <= left.size()) {
            return quickSelect(left, k);
        }

        if (left.size() + mid.size() < k) {
            return quickSelect(right, k - left.size() - mid.size());
        }

        return pivot;
    }

    int findKthLargest(vector<int>& nums, int k) {
        return quickSelect(nums, k);
    }
};

### 作法 Counting Sort
**時間: O(N+M)**

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int minValue = INT_MAX;
        int maxValue = INT_MIN;

        for (int num : nums) {
            minValue = min(minValue, num);
            maxValue = max(maxValue, num);
        }

        vector<int> count(maxValue - minValue + 1);
        for (int num : nums) {
            count[num - minValue]++;
        }

        int remain = k;
        for (int num = count.size() - 1; num >= 0; num--) {
            remain -= count[num];
            if (remain <= 0) {
                return num + minValue;
            }
        }

        return -1;
    }
};

## :memo: Kth Smallest Element in a Sorted Matrix (Medium)
Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

You must find a solution with a memory complexity better than O(n2).


### 作法
整理成一維陣列後排序

### 作法 Binary Search
**時間: O(N×log(Max−Min))**


class Solution {

  public int kthSmallest(int[][] matrix, int k) {

    int n = matrix.length;
    int start = matrix[0][0], end = matrix[n - 1][n - 1];
    while (start < end) {

      int mid = start + (end - start) / 2;
      // first number is the smallest and the second number is the largest
      int[] smallLargePair = {matrix[0][0], matrix[n - 1][n - 1]};

      int count = this.countLessEqual(matrix, mid, smallLargePair);

      if (count == k) return smallLargePair[0];

      if (count < k) start = smallLargePair[1]; // search higher
      else end = smallLargePair[0]; // search lower
    }
    return start;
  }

  private int countLessEqual(int[][] matrix, int mid, int[] smallLargePair) {

    int count = 0;
    int n = matrix.length, row = n - 1, col = 0;

    while (row >= 0 && col < n) {

      if (matrix[row][col] > mid) {

        // as matrix[row][col] is bigger than the mid, let's keep track of the
        // smallest number greater than the mid
        smallLargePair[1] = Math.min(smallLargePair[1], matrix[row][col]);
        row--;

      } else {

        // as matrix[row][col] is less than or equal to the mid, let's keep track of the
        // biggest number less than or equal to the mid
        smallLargePair[0] = Math.max(smallLargePair[0], matrix[row][col]);
        count += row + 1;
        col++;
      }
    }

    return count;
  }
}

### 作法 Max Heap

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        priority_queue<int> pq;
        
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[i].size(); j++) {
                if (pq.size() < k) {
                    pq.push(matrix[i][j]);
                }
                else {
                    pq.push(matrix[i][j]);
                    pq.pop();
                }
            }
        }
        
        return pq.top();
    }
};

## :memo: *Meeting Rooms II (Medium)
Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.



### 作法 Two pointers C
**時間: O(NlogN)**

**將會議開始時間與結束時間分別排序**，
房間++，
如果下一場會議(start指標)開始時間比現在會議(end指標)結束時間還晚，那房間--、end指標++，
直到start指標=總安排會議場數

int cmpfunc(const void* a, const void * b){
    return (*(int*) a - *(int*) b);
}

int minMeetingRooms(int** intervals, int intervalsSize, int* intervalsColSize){
    int start_ptr = 0;
    int end_ptr = 0;
    int rooms = 0;
    int* start;
    int* end;
    if (!intervalsSize)
    {
        return 0;
    }
    
    /* get the start and end timings in arrays */
    start = (int*) malloc(sizeof(int) * intervalsSize);
    end = (int*) malloc(sizeof(int) * intervalsSize);
    
    for (int i = 0; i < intervalsSize; i++)
    {
        start[i] = intervals[i][0];
        end[i] = intervals[i][1];
    }
    
    /* sort start and end arrays */
    qsort(start, intervalsSize,sizeof(int), cmpfunc);
    qsort(end, intervalsSize,sizeof(int), cmpfunc);
    
    while (start_ptr < intervalsSize)
    {
        /* keep adding new rooms for new meetings */
        rooms++;
        
        /* if one meeting has ended, reuse the room */
        if (start[start_ptr++] >= end[end_ptr])
        {
            rooms--;
            end_ptr++;
        }
    }
    
    free(start);
    free(end);
    
    return rooms;
}

### 作法 Min Heap

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());  //要先排序
        
        priority_queue<int, vector<int>, greater<int>> pq;
        
        for (auto interval : intervals) {
            if (pq.empty()) {
                pq.push(interval[1]);
            } else {
                if (interval[0] >= pq.top()) {
                    pq.pop();
                }                
                pq.push(interval[1]);
            }
        }
        
        return pq.size();
    }
};

## :memo: *K Closest Points to Origin (Medium)
Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the **X-Y** plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).

You may return the answer in **any order**. The answer is **guaranteed** to be **unique** (except for the order that it is in).



### 作法 C
這一題我用struct去添加x,y,dist三個變數，以struct攜帶去根據距離進行排序，同時把x,y一起排到相對應的順序，寫得非常耗費時間

struct node{
    int size;
    int x;
    int y;
    double dist;
};

### 作法 nth_element C++

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        nth_element(begin(points), begin(points) + k, end(points), [](vector<int> &a, vector<int> &b) {
            return a[0] * a[0] + a[1] * a[1] < b[0] * b[0] + b[1] * b[1];
        });
        
        points.resize(k);
        return points;
    }
};

## :memo: Minimum Cost to Connect Sticks (Medium)

### 作法 C
先排序後，把最短及第二短加起來的值，加到sum後，將該值放入陣列重新再排序，反覆直到陣列數為0
這一題LeetCode不之為何C不能用heap，不知道是沒寫好還是怎樣，會Time Limit Exceeded

int* A = malloc(2*sticksSize*sizeof(int));
for (int i = 0; i < sticksSize; i++) A[i] = sticks[i];
qsort(A, sticksSize, sizeof(int), comp);

int cost = 0;
while (sticksSize > 1) {
    int insertedMin = INT_MAX;
    /* if A[0] and A[1] are still smaller than any of the new sticks we can
     * keep getting new sticks without sorting.
     */
    while (stillOrdered(A, sticksSize, insertedMin)) {
        cost = cost + A[0] + A[1];
        if (insertedMin > A[0] + A[1]) insertedMin = A[0] + A[1];
        A[sticksSize] = A[0] + A[1];
        sticksSize--;
        A = A + 2;
    }
    qsort(A, sticksSize, sizeof(int), comp);
}
return cost;

### 作法 Min Heap C++

class Solution {
public:
    int connectSticks(vector<int>& sticks) {
        priority_queue<int, vector<int>, greater<int>> pq;
        int cost = 0;
        
        for (int stick : sticks) {
            pq.push(stick);
        }
        
        while (pq.size() > 1) {
            int x = pq.top();
            cost += x;
            pq.pop();
            int y = pq.top();
            cost += y;
            pq.pop();
            int combine = x + y;
            pq.push(combine);
        }
        
        return cost;
    }
};

### 作法 LC最快

class Solution {
public:
    Solution()
    {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
    }
    int pick( deque<int>& m, deque<int>& t )
    {
        int r = m.front();
        int tf;
        
        if( not t.empty() )
        {
            tf = t.front();
            if( r < tf )
                m.pop_front();
            else
            {  
                r = tf;
                t.pop_front();
            }
        }
        else
            m.pop_front();
        return r;
    }
    int connectSticks(vector<int>& s) {

        if( s.size() == 1 )
            return 0;
        int res = 0;
        sort( begin(s), end(s) );
        deque<int> md( begin(s), end(s) );
        deque<int> nd;
        int l;
        int r;
        while( true )
        {
            if( md.empty() )
                swap( md, nd );
            
            l = pick( md, nd );
            
            if( md.empty() and nd.empty() )
                break;
            
            if( md.empty() )
                swap( md, nd );
            
            r = pick( md, nd );
            
            int t = r + l;
            res += t;
            nd.push_back( t );
        }
        return res;
    }
};

## :memo: *Furthest Building You Can Reach (Medium)


### 作法 Max Heap
這一題我原本卡在一定要先用磚塊再用梯子，看了Solution後才知道要先用梯子再去用磚塊，而演算法是在用完梯子後將高度差的值插入maxHeap，之後判斷磚塊夠不夠給top的高度差值使用，夠的話就減掉top的高度差值，不夠就回傳i當最遠距離，迴圈結束代表可以走到最後一個大樓(n-1)

class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
        priority_queue<int> pq;
        
        for (int i = 0; i < heights.size() - 1; i++) {
            int d = heights[i + 1] - heights[i];
            if (d > 0) {
                pq.push(-d);
            }
            if (pq.size() > ladders) {
                bricks += pq.top();
                pq.pop();
            }
            if (bricks < 0) {
                return i;
            }
        }
        
        return heights.size() - 1;
    }
};

## :memo: Find Median from Data Stream (Hard)


### 作法
這一題完全沒想到演算法，用一個minHeap和一個maxHeap去實現，過程如上圖

class MedianFinder {
    priority_queue<int> lo;                              // max heap
    priority_queue<int, vector<int>, greater<int>> hi;   // min heap

public:
    // Adds a number into the data structure.
    void addNum(int num)
    {
        lo.push(num);                                    // Add to max heap

        hi.push(lo.top());                               // balancing step
        lo.pop();

        if (lo.size() < hi.size()) {                     // maintain size property
            lo.push(hi.top());
            hi.pop();
        }
    }

    // Returns the median of current data stream
    double findMedian()
    {
        return lo.size() > hi.size() ? lo.top() : ((double) lo.top() + hi.top()) * 0.5;
    }
};

## :memo: Tips
- **建立struct可以攜帶很多個變數**
- **在解heap題目時通常需要先進行排序**

## :memo: 刷題檢討
heap的基本定義和特性要熟練，通常題目有時候不只用到一個heap，要分析清楚再寫，heap的最重要特性就是會pop最大或最小值