Reorganize String - Implementation

function reorganizeString(s)
 count := frequency map of s
 heap := max-heap of (count, char)
 for each (char, cnt) in count
 if cnt > (length of s + 1) / 2 then
 return ""
 heap.push((cnt, char))
 result := ""
 while heap.size() >= 2
 (cnt1, c1) := heap.pop()
 (cnt2, c2) := heap.pop()
 result := result + c1 + c2
 if cnt1 > 1 then heap.push((cnt1 - 1, c1))
 if cnt2 > 1 then heap.push((cnt2 - 1, c2))
 if heap.size() = 1 then
 result := result + heap.pop().char
 return result

Time: $O(n \log k)$ where $k$ is alphabet size. Space: $O(k)$.