MinHashing vs SimHashing
As correctly pointed out above MinHash and SimHash both belong to Locality Sensitive Hashing. 
Reference: https://en.wikipedia.org/wiki/Locality-sensitive_hashing

The main difference between the two is the way collision is handled,


SimHash, uses cosine similarity
MinHash, uses Jaccard Index.


Answers to your questions:


No. They uses different collision handling techniques to validate similarity. Also there is a variant on single Hash Function for Min Hash but it works differently. For more details, check the following reference out, https://en.wikipedia.org/wiki/MinHash (Variant with a single hash function) 
Yes, https://github.com/chrisjmccormick/MinHash/blob/master/runMinHashExample.py
I think the complexity can be reduced to $O(n \log n)$ with modified form of binary search while clustering.