I have seen lots of solutions confuse `priority queue`

with `heap`

. I find a good link and list the talk below.

**Concept:**

1.`Heap`

is a kind of `data structure`

. It is a name for a particular way of storing data that makes certain operations very efficient. We can use a tree or array to describe it.

```
18
/ \
10 16
/ \ / \
9 5 8 12
18, 10, 16, 9, 5, 8, 12
```

2.`Priority queue`

is an `abstract datatype`

. It is a shorthand way of describing a particular interface and behavior, and says nothing about the underlying implementation.

A heap is a very good data structure to implement a priority queue. The operations which are made efficient by the heap data structure are the operations that the priority queue interface needs.

**Implementation: c++**

1.`priority_queue`

: we can only get the top element (from ChiangKaiShrek's solution)

```
struct compare {
bool operator()(const ListNode* l, const ListNode* r) {
return l->val > r->val;
}
};
ListNode *mergeKLists(vector<ListNode *> &lists) { //priority_queue
priority_queue<ListNode *, vector<ListNode *>, compare> q;
for(auto l : lists) {
if(l) q.push(l);
}
if(q.empty()) return NULL;
ListNode* result = q.top();
q.pop();
if(result->next) q.push(result->next);
ListNode* tail = result;
while(!q.empty()) {
tail->next = q.top();
q.pop();
tail = tail->next;
if(tail->next) q.push(tail->next);
}
return result;
}
```

2.`make_heap`

: we can access all the elements (from my answer for that solution)

```
static bool heapComp(ListNode* a, ListNode* b) {
return a->val > b->val;
}
ListNode* mergeKLists(vector<ListNode*>& lists) { //make_heap
ListNode head(0);
ListNode *curNode = &head;
vector<ListNode*> v;
for(int i =0; i<lists.size(); i++){
if(lists[i]) v.push_back(lists[i]);
}
make_heap(v.begin(), v.end(), heapComp); //vector -> heap data strcture
while(v.size()>0){
curNode->next=v.front();
pop_heap(v.begin(), v.end(), heapComp);
v.pop_back();
curNode = curNode->next;
if(curNode->next) {
v.push_back(curNode->next);
push_heap(v.begin(), v.end(), heapComp);
}
}
return head.next;
}
```

If there is something wrong, please figure it out. Hoping to learn more about them.